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;
        }
    }
}


回到顶部