leetcode——单调递增栈——862. 和至少为 K 的最短子数组

思路：

1. 求的是和至少为 K 的连续最短子数组，首先利用数组prefixSum保存【0~i】的前缀和为多少，容易知prefixSum[j]-prefisxSum[i]，表示 i+1~j 的和，因此将问题转化为求以 不同元素结尾时的和至少为 K 的连续最短子数组，要求这个 result[j]其实就是比较所有prefixSum[j]-prefixSum[i](i<j)的情况，如果前缀和相减大于等于 K，则符合情况，将该区间长度与最短长度进行比较，可以直到对于prefixSum[j]-prefixSum[i](i<j)，如果存在prefixSum[p]>prefixSum[q],且 p<q,则prefixSum[j]-prefixSum[q]肯定大于prefixSum[j]-prefixSum[p]，而且前者的区间长度更短，因此在求prefixSum[j]-prefixSum[i](i<j)时，需要用到的不是所有 i<j，而是：如果在【0~i】中出现“prefixSum[p]>prefixSum[q]”的情况，那么可以舍弃prefixSum[p]，即只需要prefixSum[i](i<j)中哪些单调递增的前缀和
2. 如果在对prefixSum[j]-prefixSum[i](i<j，且单调递增)进行从左到右遍历时，发现最左（双端队列头部）的元素满足条件，则将它弹出，直到不能再弹出（每次都取其区间长度与 min 进行比较），弹出的原因是，该区间[i+1~j]构成满足条件的区间，队列内不需要再保存prefixSum[i]，因为对于右边界在 j 后的情况来说，不需要在对左边界为 i+1的情况进行判断，因为不管满不满足条件，其区间长度都比 min 大

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

难度困难274

返回 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

// import Math
class Solution {
    //思路：
    //优化：1.继续要得到头或尾的值，又需要弹出头或尾，应用弹出的返回值直接得到其值（而不是分两步）,其实好像相差并不大。。甚至这样还会变慢哈哈哈哈哈哈  2.单调栈还是只加入坐标比较好，利用坐标从数组取对应值（而不是将他们都对应着一起入栈）
    public int shortestSubarray(int[] A, int K) {
        int n=A.length;
        //int[] prefixSum=new int[n];
        //prefixSum[0]=A[0];
        int[] prefixSum=new int[n+1];
        for(int i=1;i<prefixSum.length;i++){
            prefixSum[i]=prefixSum[i-1]+A[i-1];
        }
        Deque<Integer> deque=new LinkedList<>();

        //deque.addLast(new int[]{0,-1});
        int min=n+1;
        for(int i=0;i<n+1;i++){
            //stack.peek()[0]
            while(!deque.isEmpty()&&prefixSum[i]<=prefixSum[deque.peekLast()]){
                deque.removeLast();
            }
            while(!deque.isEmpty()&&prefixSum[i]-prefixSum[deque.peekFirst()]>=K){
                int l=i-deque.removeFirst();
                min=Math.min(min,l);
            }
            // for(int[] a:deque){
            //     if(prefixSum[i]-a[0]>=K){
            //         int l=i-a[1];
            //         min=Math.min(min,l);
            //     }
            // }
            deque.addLast(i);

        }
        return min==(n+1)?-1:min;
        
    }
}

/*
class Solution {
    public int shortestSubarray(int[] A, int K) {
        int min=50001;
        int n=A.length;
        int left=0,right=1;
        int sum=A[0];
        if(A[0]>=K) return 1;

        while(right<n){
            if(A[right]>=K) return 1;
            
            if(sum<=0){
                left=right;
                sum=A[left];
                right++;
                continue;
            }

            sum+=A[right];

            
            if(sum>=K){  //sum==K 则 left 不能缩，
                min=Math.min(min,right-left+1);
                int tempSum=A[right];
                int temp=right;
                while(tempSum<K&&temp>left){
                    tempSum+=A[--temp];
                }
                left=temp;
                sum=tempSum;
                min=Math.min(min,right-left+1);
                left++;


                // while(left<right){
                //     //sum-A[left]>=K
                //     sum-=A[left];
                //     left++;
                //     if(sum>=K) min=Math.min(min,right-left+1);
                // }
            }
            //
            

            //left~right是最短的了

            right++;
        }
        return min==50001?-1:min;
    }
}
*/