温故：队列|数据结构

本文将对数据结构 - 队列 进行温故、总结要点、算法题练手，以期获新知。

读者可以借本文反视对队列知识的掌握程度，或者在本文基础上，收集资料加深学习。

温故系列是我尝试的一种新学习总结方式，在 阅历增长时，总结旧闻，以 期获 新知，并不断迭代。了解更多

本次温故时间：2021年3月

队列，和栈类似, 也是一种线性存储结构，不同的是，队列的数据项存取方式，队列是两端 开口 的，从数据从一端进入，从另一端取出。

进入的一端被称为 队尾，取出的一端被称为 队头，存入数据的行为称为 入队，取出数据的行为称为 出队。

不难理解，这是一种 先进先出 的线性存储结构。

和栈类似，实现方式也存在两种：

顺序队列：在顺序表的基础上实现的队列结构
链队列：在链表的基础上实现的队列结构

Android中的消息队列，就是链队列

在Java中，队列对应 java.util.Queue

public interface Queue<E> extends Collection<E> {
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

offer，add：达到容量上限时，继续尝试入队时，add 会抛出异常，offer 返回 false
poll，remove：空集时，remove 会抛出异常，poll 返回 null
peek，element：空集时 element 会抛出异常，peek 返回null

算法题练手

我在LeetCode上，搜索了一道和队列相关的题。

和至少为 K 的最短子数组

返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。

如果没有和至少为 K 的非空子数组，返回 -1 。

示例 1：

输入：A = [1], K = 1
输出：1

示例 2：

输入：A = [1,2], K = 4
输出：-1

示例 3：

输入：A = [2,-1,2], K = 3
输出：3

提示：

1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k

乍一看到这个题目，我也有点慌，没啥思路。

但是没关系，我们假设存在一个算法S，可以处理这个问题。从比较基本的情况找到可行的处理方式，并利用数学归纳法进行证明。然后在实现算法。

按照题意，需要寻找非空子数组，其和>=K , 设函数 F(s,e) = ∑_s^eA[i], s,e 满足 0≤s≤e≤A.length。

并且我们用其代表对于的子数组。

我们先找到所有的子数组。

当length为

1 时，子数组 1个，F(0,0)
2 时，子数组 3个，F(0,0),F(1,1),F(0,1)
3 时，子数组 6个，F(0,0),F(1,1),F(2,2)，F(0,1),F(1,2),F(0,2)
...
n 时，子数组 (n+1)(n)/2 个

不难理解，长度为n时，n>0，长度为 a 的子数组个数为 n-a+1 个，我们把a的所有取值情况都考虑进去，就可以得到所有的子数组，空数组不计，这实在是太简单了，我们不再使用数学归纳法论证。

我们先通过一次遍历，得到一组基础情况：

F(0,0),F(0,1),F(0,2),...,F(0,n-1)

在此基础上，我们可以得到

       F(1,1),F(1,2),...,F(1,n-1)

              F(2,2),...,F(2,n-1)

...

                         F(n-1,n-1)

不难理解，做法就是遍历 A[i],并在原先的基础上减掉对应值。

下面的代码，我们就可以得到 基础 情况

class Solution {
    public int shortestSubarray(int[] A, int K) {
        int n = A.length;
        //可能会溢出，用long，第一个元素保持为0
        long[] P = new long[n + 1];
        for (int i = 0; i < n; i++) {
            P[i + 1] = P[i] + (long) A[i];
        }

        return -1;
    }
}

得到每一层数据。

class Solution {
    public int shortestSubarray(int[] A, int K) {
        int n = A.length;
        //可能会溢出，用long，第一个元素保持为0
        long[] P = new long[n + 1];
        for (int i = 0; i < n; i++) {
            P[i + 1] = P[i] + (long) A[i];
        }

        // 遍历 得到每一层数据
        for (int i = 1; i < n; i++) {
            for (int j = i; j < n; j++) {
                long tmp = P[j + 1] - A[i - 1];

                P[j + 1] = tmp;
            }
        }


        return -1;
    }
}

F(s,e) = F(i,j)

ok，我们需要找到映射关系，即 i,j 和前面 s,e 的对应关系。

不难得出: s=i,e=j

而F(s,e)，对应的数组长度 len = e-s+1;

class Solution {
    public int shortestSubarray(int[] A, int K) {
        int n = A.length;
        int len = n + 1;

        //可能会溢出，用long，第一个元素保持为0
        long[] P = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            long tmp = P[i] + (long) A[i];

            if (tmp >= K) {
                len = Math.min(len, i + 1);
            }

            P[i + 1] = tmp;
        }

        // 遍历 得到每一层数据
        for (int i = 1; i < n; i++) {
            for (int j = i; j < n; j++) {
                long tmp = P[j + 1] - A[i - 1];
                if (tmp >= K) {
                    len = Math.min(len, j - i + 1);
                }

                P[j + 1] = tmp;
            }
        }

        if (len > n)
            return -1;
        return len;
    }
}

居然。。没有用到队列！！！

然而现实比较残酷，这个解法 超出了时间限制，跪在了 84/93 用例上

那就想想如果减少计算次数吧:

f(i,j) 还有一种求法，f(0,j)-f(0,i-1),即 P[j+1]-P[i]

但也仅多通过了一个用例。

仔细思考了一下，力大砖飞法为什么不能通过 时间限制？因为这个方法中，进行了 全计算。

我们先做一个假设：数组中全是正数。

那么从下标s开始，对下标i=s开始递增，一旦找到下标e满足 F(s,e)>=K ,那么就没有必要再对i进行递增了。

再回到我们的题目中，我们已近先计算了一组 基础数据 : P[]，而且前面我们发现了，利用 基础数据 本身，以及 减法计算 ，可以表达整个数组的任意 非空子数组。

那么,这个问题从

"在<s,e> 满足F(s,e)>=K 条件的集合中，寻找 e-s的最小值"

转变成了：

在<s,e> 满足P[e+1]-P[s]>=K 条件的集合中，寻找 e-s的最小值

经过这一步转化，就可以运用数学定理减少计算了。

因为有负数的存在，在P[] 中，其 元素值 并不是 随着 下标 而 单调递增 的。

采用示例3：输入：A = [2,-1,2], K = 3

那么P[] = [0,2,1,3]

我们发现，它不是单调递增的，但是这里有一个规律：

P[3]-P[2] > P[3]-P[1]

即，3-1 > 3-2

如果P[3]-P[2] 不满足要求，那么P[3]-P[1]也无法满足要求
如果P[3]-P[2] 满足要求，那么P[3]-P[1] 是否满足已经不再重要，即使满足，长度也更大，而且，判断是否满足还需要计算，无法直接通过不等式关系推算

从这里，我们可以总结出：当P[i]>P[i+1] 时，不需要考虑 F(i,待定) 是否满足要求。

这样我们就把问题简化到了单调情况。即，s的取值范围，仅需要考虑： {0,2,3},因为 P[1]>P[2]

而且，在前面的分析中，发现都是正数的数组时：

从下标s开始，对下标i=s开始递增，一旦找到下标e满足 F(s,e)>=K ,那么就没有必要再对i进行递增了。

这一点在存在负数时也同样成立。

稍微打住，直觉告诉我，还有进一步优化的空间，那就是e的取值范围可以进一步缩小。

我们发现 P[2]-P[0] < P[1]-P[0]。所以e不需要考虑为2的情况，取值范围{0,1,3}.

则：<s,e> 仅需要考虑 {<0,0>,<0,1>,<0,3>,<2,3>,<3,3>} 这几种情况。

不难理解：此时再利用 数组结合For循环两组下标的方式 已经无法处理了，有必要引入新的数据结构，利用其特性完成这一任务。

而 双端队列 可以满足这一需求。

我们维护一个双端队列 deque，用于存储P的下标，
遍历 P的下标 index
假如index 存入deque尾部，需要保持 deque 所有下标对应的P值单调递增，如果不满足这个要求，则先从尾部移除，直到 deque为空 或者 满足单调递增
寻找 index 作为 e 时，满足条件的最适s，即最大s，如果找到，则维护最短的len值； 这里又有一个减少计算的小窍门前面没有明确提到
index 从尾部入队

做法中，提到了一个小技巧：

在前文，我们提到了:从下标s开始，对下标i=s开始递增，一旦找到下标e满足 F(s,e)>=K ,那么就没有必要再对i进行递增了。

这其实是相对的。一旦找到这样一组<s,e>, 当e递增时，s直接从s+1开始考虑即可。

所以这个小技巧就是将 deque 的队头出队

class Solution {
    public int shortestSubarray(int[] A, int K) {
        int n = A.length;
        int len = n + 1;

        //可能会溢出，用long，第一个元素保持为0
        long[] P = new long[n + 1];
        for (int i = 0; i < n; ++i) {
//                long tmp = P[i] + (long) A[i];

            //其实重复了，后面的遍历中也有对应
//                if (tmp >= K) {
//                    len = Math.min(len, i + 1);
//                }

            P[i + 1] = P[i] + (long) A[i];
        }

        final LinkedList<Integer> deque = new LinkedList<>();

        //用前置++ 减少临时变量分配内存消耗时间
        for (int index = 0; index < n + 1; ++index) {
            while (!deque.isEmpty() && P[deque.getLast()] >= P[index]) {
                deque.removeLast();
            }

            while (!deque.isEmpty() && P[index] - P[deque.getFirst()] >= K) {
                len = Math.min(len, index - deque.removeFirst());
            }

            deque.add(index);
        }

        if (len > n)
            return -1;
        return len;
    }
}

修改后通过测试用例。

温故总结

队列也是非常常用的数据结构了，其特性需要牢牢掌握。

算法练手阶段出了纰漏，筛选的题目并没有着重于队列的特性。

leobert's blog

温故：队列|数据结构

算法题练手

和至少为 K 的最短子数组

温故总结