Skip to content

862. Shortest Subarray with Sum at Least K

862. Shortest Subarray with Sum at Least K

题目: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k

难度: Hard

题意：

  1. 给定一个数组A
  2. 求A的所有连续子数组中，和大于K，最短的一个，长度是多少

思路：

  • 如果A里面都是正整数，那就是一个妥妥的移动区间，可惜有负数
  • 换种思路，A[i...j] = sum[1..j] - sum[1..i-1]，我们可以从前往后累加，当累加到j时，我们只需要把前面sum[1..1]到sum[1..j-1]的累加值中寻找一个最大的i，使得sum[1..j] - sum[1..i-1] >= K，复杂度是o(n^2)，是不可接受的
  • 注意到，当我们累加到j，如果存在一个i，使得sum[1..i] <= sum[1..i + 1]，那么，假设sum[1..j] - sum[1..i] >= K，那么sum[1..j] - sum[1..i + 1] 肯定也是 >= K，所以当sum[1..i + 1]存在时，sum[1..i] 没有存在的意义。因此，我们只需要维护一个单调递增队列sum[1..a1],sum[1..a2],...sum[1..am]，其中sum[1..a1] < sum[1..a2] < .... ，a1 < a2 < ...
  • 有了单调递增队列，当遍历到j，我们只需要二分这个队列，就可以找到一个最大的i，使的sum[1..j]-sum[1..i] >= K，插入一个数到单调队列，只需要从队列尾开始比较，把比要插入的数大的都出列，维持单调递增特性
  • 复杂度是o(nlogn)

代码：

class Solution {
    private class Node {
        int sum;
        int pos;

        public Node(int sum, int pos) {
            this.sum = sum;
            this.pos = pos;
        }
    }

    private int find(Node[] incrQueue, int n, int value) {
        int left = -1;
        int right = n;
        while (right - left > 1) {
            int mid = (left + right) / 2;
            if (incrQueue[mid].sum <= value) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public int shortestSubarray(int[] A, int K) {
        Node[] incrQueue = new Node[A.length + 1];
        int n = 0;
        int ret = 0x3fffffff;
        incrQueue[n++] = new Node(0, -1);
        int sum = 0;
        for (int i = 0;i < A.length;i++) {
            sum += A[i];
            int pos = find(incrQueue, n, sum - K);
            if (pos != -1) {
                ret = ret < (i - incrQueue[pos].pos) ? ret : (i - incrQueue[pos].pos);
            }
            while (n != 0 && incrQueue[n - 1].sum > sum) {
                n--;
            }
            incrQueue[n++] = new Node(sum, i);
        }
        if (ret == 0x3fffffff) {
            return -1;
        } else {
            return ret;
        }
    }
}
回到顶部