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

贾蔷
• 阅读 9

动态规划预处理+滑动窗口:力扣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年前
PTA1
11数组定义中,数组名后是用方括号括起来的常量表达式,不能用圆括号。(1分)\T\F12在C语言中能逐个地使用下标变量,也能一次引用整个数组。(1分)T\F\因为它有首地址13同一个数组中的每个元素都具有相同的数据类型,有统一的标识符即数组名,用不同的序号即下标来区分数组中的各元素。(1分)\T\F14数
Wesley13 Wesley13
3年前
JS 获取数组某个元素下标 函数方法
/获取某个元素下标arrays:传入的数组obj:需要获取下标的元素/functioncontains(arrays,obj){variarrays.length;w
Wesley13 Wesley13
3年前
Java中的数组(Array)
数组对于每一门编程语言来讲都是最重要的数据结构之一,当然不同的编程语言对数组的实现以及处理也不尽相同。数组的概念:把有限个相同类型元素变量放在一个整体,这个整体就叫做数组。数组中的每一个元素被称为数组元素,通常可以通过数组元素的索引(也叫下标,可以理解为一种编号,从0开始)来访问数组元素,包括数组元素的赋值(set)和取值(get)。
Wesley13 Wesley13
3年前
JavaSE
DAY081.数组1.1定义数组是相同类型数据的有序集合。数组描述的是相同类型的若干个数据,按照一定的先后次序排列组合而成。其中,每一个数据称作一个元素,每个元素可以通过一个索引(下标)来访问它们。数组的三个基本特点:1.长度是确定的。数组一旦被创建,它的大小就是不可以改变的。2.其元素必须
Wesley13 Wesley13
3年前
Java基础语法:数组
一、简介描述:数组是相同类型数据的有序集合。其中,每一个数据称作一个数组元素,每个数组元素可以通过一个下标来访问它们。基本特点:1.数组的长度是确定的。数组一旦被创建,它的大小就是不可以改变的。2.数组元素必须是相同类型,不允许
贾蔷 贾蔷
7小时前
牛客3750题滑动窗口最大值解析:双端队列优化解法与代码详解
一、题目解读要求在一个给定的整数中,计算固定大小为k的内元素的最大值。例如,当窗口滑动时,需要实时输出每个窗口中的最大值序列。该问题考察对的理解,以及如何高效维护窗口内的元素关系。二、解题思路采用(deque)维护的巧妙解法。核心思想是:中仅存储数组下标,
贾蔷 贾蔷
1个月前
力扣501题 解题思路和步骤 C++代码实现,力扣(leetcode)
问题背景及描述力扣501题要求我们找出在一个二叉搜索树(BST)中的众数。二叉搜索树是一种特殊的二叉树,其中每个节点的值都大于其左子树中的任何节点,且小于其右子树中的任何节点。众数是指在BST中出现次数最多的值。解题思路分析解题的关键在于理解BST的性质以
深度学习 深度学习
1星期前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
深度学习 深度学习
1星期前
动态规划进阶:牛客4802题带附件背包问题详解 | 组合优化技巧
一、问题背景与算法思路牛客4802题是一个典型的带附件的背包问题变种,要求在主件和附件存在依赖关系的情况下,选择物品组合使总价值最大化。本文通过动态规划方法,将问题转化为分组背包问题,通过预处理所有可能的组合方式来实现高效求解。二、完整代码实现(带详细注释