动态规划预处理+滑动窗口:力扣2420题"好下标"解法详解

贾蔷
• 阅读 66

动态规划预处理+滑动窗口:力扣2420题

一、问题理解

题目要求找出数组中满足特定条件的"好下标":对于下标i,其左侧k个元素必须是非递增的,右侧k个元素必须是非递减的。这是典型的数组区间性质检查问题。

二、解题思路

1. 动态规划预处理

核心思想是通过两次预处理:

  • left数组:记录每个位置向左的非递增序列长度
  • right数组:记录每个位置向右的非递减序列长度

2. 完整代码解析

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;
        vector<int> left(n, 1);  // 初始化:每个元素至少可以形成长度为1的序列
        vector<int> right(n, 1); // 同上

        // 从左到右预处理left数组
        for (int i = 1; i < n; ++i) {
            if (nums[i] <= nums[i-1]) {
                left[i] = left[i-1] + 1; // 满足条件时继承前一个位置的长度+1
            }
        }

        // 从右到左预处理right数组
        for (int i = n-2; i >= 0; --i) {
            if (nums[i] <= nums[i+1]) {
                right[i] = right[i+1] + 1; // 同理处理右侧
            }
        }

        // 滑动窗口检查有效下标
        for (int i = k; i < n - k; ++i) {
            // 检查左右两侧是否都满足k长度要求
            if (left[i-1] >= k && right[i+1] >= k) {
                res.push_bACk(i);
            }
        }

        return res;
    }
};

三、关键点分析

  1. 预处理优化:O(n)时间完成两次遍历,避免每次检查都重复计算
  2. 边界处理:注意i的取值范围是[k, n-k-1]
  3. 空间换时间:使用两个额外数组存储中间结果

四、复杂度分析

  • 时间复杂度:O(n) 三次线性遍历
  • 空间复杂度:O(n) 需要两个辅助数组

五、实际应用

这种预处理+滑动窗口的组合方法在解决数组区间问题时非常高效,类似的思路可以应用于:

  • 股票买卖问题
  • 雨水收集问题
  • 最大子数组问题

来源:动态规划预处理+滑动窗口:力扣2420题"好下标"解法详解

点赞
收藏
评论区
推荐文章
好买-葡萄 好买-葡萄
3年前
【数据结构与算法】—— 二分查找
1.二分查找的概念二分查找指的是在排好序的数组中,找到目标元素。如果元素存在则返回元素的下标,不存在则返回1.下面以升序为例进行简单描述2.查找过程:取数组中间元素与查找元素target比较。如果target等于中间元素则直接返回中间元素的下标,如果target小于数组中间元素则在数组左边查找,如果target大于数组中间元素则在右边查找。重复以上步骤。
Wesley13 Wesley13
3年前
Java中的数组(Array)
数组对于每一门编程语言来讲都是最重要的数据结构之一,当然不同的编程语言对数组的实现以及处理也不尽相同。数组的概念:把有限个相同类型元素变量放在一个整体,这个整体就叫做数组。数组中的每一个元素被称为数组元素,通常可以通过数组元素的索引(也叫下标,可以理解为一种编号,从0开始)来访问数组元素,包括数组元素的赋值(set)和取值(get)。
Wesley13 Wesley13
3年前
JavaSE
DAY081.数组1.1定义数组是相同类型数据的有序集合。数组描述的是相同类型的若干个数据,按照一定的先后次序排列组合而成。其中,每一个数据称作一个元素,每个元素可以通过一个索引(下标)来访问它们。数组的三个基本特点:1.长度是确定的。数组一旦被创建,它的大小就是不可以改变的。2.其元素必须
Wesley13 Wesley13
3年前
Java基础语法:数组
一、简介描述:数组是相同类型数据的有序集合。其中,每一个数据称作一个数组元素,每个数组元素可以通过一个下标来访问它们。基本特点:1.数组的长度是确定的。数组一旦被创建,它的大小就是不可以改变的。2.数组元素必须是相同类型,不允许
贾蔷 贾蔷
2星期前
2024蓝桥杯省赛B组“传送阵”题解
一、题目解读2024年省B组“传送阵”题目要求处理一个包含n个节点的,节点间存在单向传输关系。每个节点i可传送至a中的最长路径问题,需考虑环的存在及节点间的连通性。二、解题思路1.预处理阶段使用标记法找出所有环,记录每个环的大小(即节点数)。2.统计最大环
深度学习 深度学习
2星期前
牛客网235698题:用滑动窗口寻找最多包含两种字符的最长子串
一、什么是?是一种用于处理/子区间问题的技术。它通过维护一个窗口(通常是子数组或子字符串),在遍历过程中动态调整窗口的边界,从而高效地解决问题。二、算法核心思想1.‌初始化窗口‌:通常从数组/字符串的起始位置开始1.‌扩展窗口‌:移动右边界,扩大窗口范围1
深度学习 深度学习
1星期前
LeetCode 2576题解:双指针法求解最多标记下标(排序+贪心策略)
一、题目解读2576题要求在一个整数中寻找最多可标记的下标对:若nums法”的组合思路:1.排序预处理:对原数组nums进行升序排序,确保相同元素聚集,便于后续配对。2.双划分:将排序后的数组分为左右两半(左指针left0,右指针rightn/2),从
贾蔷 贾蔷
1个月前
力扣501题 解题思路和步骤 C++代码实现,力扣(leetcode)
问题背景及描述力扣501题要求我们找出在一个二叉搜索树(BST)中的众数。二叉搜索树是一种特殊的二叉树,其中每个节点的值都大于其左子树中的任何节点,且小于其右子树中的任何节点。众数是指在BST中出现次数最多的值。解题思路分析解题的关键在于理解BST的性质以
深度学习 深度学习
1个月前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
贾蔷 贾蔷
2星期前
牛客3750题滑动窗口最大值解析:双端队列优化解法与代码详解
一、题目解读要求在一个给定的整数中,计算固定大小为k的内元素的最大值。例如,当窗口滑动时,需要实时输出每个窗口中的最大值序列。该问题考察对的理解,以及如何高效维护窗口内的元素关系。二、解题思路采用(deque)维护的巧妙解法。核心思想是:中仅存储数组下标,