至少为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)

代码：

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

该分类下的相关小册推荐：

编程之道-算法面试(上)

业务开发实用算法精讲

数据结构与算法之美

算法面试通关 50 讲

编程之道-算法面试(下)

数据结构与算法(上)

数据结构与算法(下)