Keshawn_lu's Blog

Leetcode 862. 和至少为 K 的最短子数组

双端队列
字数统计: 563阅读时长: 2 min
2022/10/26 Share

题目简介：

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

示例 1：

1
2
输入：nums = [1], k = 1
输出：1

示例 2：

1
2
输入：nums = [1,2], k = 4
输出：-1

示例 3：

1
2
输入：nums = [2,-1,2], k = 3
输出：3

提示：

  • 1 <= nums.length <= 10^5
  • -10^5 <= nums[i] <= 10^5
  • 1 <= k <= 10^9

思路：

首先计算出每个元素的前缀和并保存下来。

我们可以考虑以下两种情况：

  1. dp[i] - dp[j] >= k，此时无论i后面的元素z是什么，z - j的长度必定大于i - j，因此我们就不需要j了，将其删除。

  2. dp[i] <= dp[j]，此时无论i后面的元素z是什么，dp[z] - dp[i]必定大于等于dp[z] - dp[j]，因此我们也不需要j了，将其删除。

通过第二种情况的优化，我们可以发现dp[i]会形成一个递增序列。

所以当我们优化第一种情况时，可以从前面开始删除（dp[j]逐渐增大）；

优化第二种情况时，便从后面开始删除（dp[j]逐渐变小），直到dp[j] < dp[i]时停止；

  • 注意遍历到dp[i]时，无论是从后面还是从前面开始删除，删除的元素j都是小于i的（即j在i的前面）。

因此我们需要一个可以从两端删除元素的数据结构，所以我们使用双端队列deque。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {

        int res = -1;

        vector<long> dp(nums.size() + 1);

        for(int i = 0; i < nums.size(); i++)
            dp[i + 1] = dp[i] + nums[i];


        deque<int> qu;
        for(int i = 0; i <= nums.size(); i++){

            //从左端开始删除
            while(!qu.empty() && dp[i] - dp[qu.front()] >= k){
                
                if(res == -1)
                    res = i - qu.front();
                else
                    res = min(res, i - qu.front());
                
                qu.pop_front(); //元素后续无用，弹出
            }

            //从右端开始删除
            while(!qu.empty() && dp[i] <= dp[qu.back()]){
                
                qu.pop_back(); //元素后续无用，弹出
            }

            qu.push_back(i);
        }

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网