作者： CheungQ

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

 

示例 1：

输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

示例 2：

输入：arr = [11,81,94,43,3]
输出：444

 

提示：

• 1 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

 

\n

题解

import java.util.Stack;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private int sum = 0;

    public int sumSubarrayMins(int[] arr) {

        Stack<int[]> stack = new Stack<>();
        int tmp = 0;
        for (int i = 0; i < arr.length; i++) {
            int count = 1;
            //边界条件等于的情况，后来的数字如果和前面已经入栈的数字大小相同，拿后来的数字覆盖前面的，
            while (!stack.isEmpty() && arr[i] <= stack.peek()[0]){
                int[] top = stack.pop();
                count += top[1];
                tmp -= top[1] * top[0];
            }
            tmp += arr[i] * count;
            sum += tmp ;
            stack.push(new int[]{arr[i],count});

            if (sum >= 1000000007){
                sum -= 1000000007;
            }
        }

        return sum;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。

示例 2：

输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

示例 3：

输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

 

提示：

• n == nums.length
• 1 <= n <= 2 * 105
• -109 <= nums[i] <= 109

\n

题解

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean find132pattern(int[] nums) {
        Deque<Integer> deque = new ArrayDeque<>();
        int pollMax = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (deque.isEmpty()){
                deque.offer(i);
                continue;
            }
            if ( nums[i] < pollMax ){
                return true;
            }
            //维护递增
            while ( !deque.isEmpty() && nums[i] > nums[deque.peekLast()] ){
                int lastPollIndex = deque.pollLast();
                pollMax = Math.max(pollMax,nums[lastPollIndex]);
            }
            deque.offer(i);
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

 

提示：

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

\n

题解

看到题目第一个想到的想法是，找峰值，找到峰值之后，找下一个峰值，这样计算两个峰值之间能够的储水量。然后接下来再去后面继续找峰值，但是新的峰值和前面的峰值之间的储水面积之间是有可能有重合的。

那么有什么办法来计算去掉重合的面积嘛？标记已计算部分也行可行，但是计算起来比较麻烦。拿自己凑的一个数组举例如图数组【7,5,4,1,3,6,2,9】

如果按照之前的思路可以得到这样的情况

后面的复杂形状的计算逻辑有点麻烦，但是这个时候换了个想法看了下。我们其实可以横着来计算，思路都在这张图上了。

依旧是找到第一个峰值，左边的都可以丢掉不管，因为第一个峰值左边的部分储不了水。从峰值开始，每个索引的值按照单调递减入栈，当有新的值比栈顶的值大的时候说明有开始呈上升趋势了，有开始上升的时候就说明这个时候是可以储水的了。

比如图中的索引4位置的值是3，当前栈内元素，按照从栈顶到栈底的顺序依次为1,4,5,7（实际栈内存的索引位置，后面默认都是不做额外说明）。

则可以计算得到A区域的面积，栈顶元素弹出，此时最新栈顶元素为4，而当前的3与4之间要储水的话，需要取小的一个，就是3，再减去之前弹出的栈顶元素1作为底部高度，那么这段区间可以储水面积就是3×1=3。并把3压入栈。

再往后到了索引5的位置，此时栈内元素为3,4,5,7。因为6大于3，把栈顶元素3出栈，按照之前同样的逻辑，6和此时栈顶的4比较取4，那么就得到了图中B区域的面积（4-3）x（5-2-1） = 2。继续和栈顶元素比较，6大于4，将4弹出，相同的操作，得到C区域的面积，同样的算出D区域的面积。最终将5位置6压入栈。

此时栈中元素为6,7。然后来到了索引6，索引6位置2小于此时小于栈顶的6，直接压入栈。之后到了索引7，再算出E，F区域的面积。最终即为所求总储水量。

代码

import java.util.ArrayDeque;
import java.util.Deque;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int area = 0;

    public int trap(int[] arr) {
        if (null==arr||arr.length==0)return area;
        int left = 0;
        int index = 0;
        //找出第一个左边
        while (index < arr.length-1){
            if (arr[index] >= arr[left]){
                left = index;
            }else{
                break;
            }
            index++;
        }
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(left);
        //此时的left一定是第一个最高点
        for (int currentIndex = left; currentIndex < arr.length; currentIndex++) {
            if (currentIndex > 0 && arr[currentIndex]>arr[currentIndex-1]){
                while (!deque.isEmpty() && arr[currentIndex] >= arr[deque.peekLast()]){
                    int bottomIndex = deque.pollLast();
                    if (deque.isEmpty()){
                        break;
                    }
                    int leftIndex = deque.peekLast();
                    int height = Math.min(arr[currentIndex],arr[leftIndex]) - arr[bottomIndex];
                    int width = currentIndex - leftIndex - 1;
                    area += height * width;
                }

            }
            deque.offerLast(currentIndex);
        }
        return area;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

 

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

\n

题解

直接说官方题解的思路，已测试用例【2,1,5,6,2,3】来说，在左侧-1，和6的索引上各新增一个虚拟节点，值为0。

从左开始遍历，我们可以先在栈中压入一个-1作为打底。此处用Deque代替Stack使用，根据网友的说法Java 因为历史的原因 Stack 这个类设计得不好，官方建议使用Deque，只使用特定的方法从队位插入，从队尾弹出来模拟实现。具体可能需要看下Stack的底层源码实现。

0）回归正题，当索引走到0的时候，对应的值2，对比栈顶当前索引-1对应的值0，2>0，那么我们直接把索引0压入栈。此时栈中情况为-1,0

1）当索引到1的时候对应的值1，对比栈顶索引0，对应的值2，1<2，将2弹出，找到2高度为当前的2的时候能取得的最大面积的宽度，为当前的的索引1到当前栈顶0取出后的栈顶索引0之间的距离，为1。所以2对应的面积为2×1 = 2，对应索引0。

在索引0弹出后，将索引1压入栈，当前栈中的情况为-1,1

2）继续遍历下一个当前索引2，对应的值为5,对比栈顶索引1对应的值1，5大于1，所以直接压入栈。

3）继续遍历下一个当前索引3，对应的值为6，对比当前栈顶索引2对应的值5，6大于5，直接压入栈。

4）继续遍历下一个，当前索引4，对应的值2，2比6小，弹出栈顶索引3，并得到对应宽度为栈顶索引3弹出后的栈顶索引位置2，那么宽度就是4到2之间的距离个数4-2-1为1个，于是得到了当前位置的6对应的最大面积6×1=6。

到目前位置已经知道的索引0位置的2对应的面积2，索引3位置的6对应的面积6。那么当前的最大面积就是6了。

在索引3位置的6弹出后，当前索引4位置的2依旧还要和当前栈顶索引2的5对比。而5大于2，继续做相同的处理，将索引2弹出，栈中索引2的前一个索引是1，所以2位置的5对应的面积为5x(4-1-1) = 10。此时最大值面积为10。

直到栈顶索引1对应的值1小于当前索引4对应的值2，将当前索引4压入栈

5）下一个循环，当前索引5，对应的值3，比当前栈顶索引4对应的值2大，直接压入栈

6）再下一个循环，数组部分的值已经结束，当前索引6，对应的值为我们之前虚拟的值0，而0小于3。弹出栈顶索引5，索引5对应的值为3，栈中索引5的前一个是索引4，那么可以知道索引5的高度3对应能取到的最大宽度为6-4-1 = 1，对应面积为3。当前最大面积依旧是10。

在栈顶索引5弹出后，当前栈顶索引是4，对应的值2也大于0，继续弹出栈顶索引4，对应值2。同样的，栈顶索引4的前一个是1，当前位置的2能取得的最大宽度是6-1-1 = 4，最大面积为2×4 =8。最大面积还是10。

索引4弹出后，继续往前对比索引1，1大于0，同样的操作。

最终结束。

下面是代码

import java.util.ArrayDeque;
import java.util.Deque;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    private int max = 0;
    private int[] arr;
    public int largestRectangleArea(int[] heights) {
        arr = heights;
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(-1);
        for (int i = 0; i <= arr.length; i++) {
            int num = getNumByIndex(i);
            int dequeLastIndex = deque.peekLast();
            int dequeLastNum = getNumByIndex(dequeLastIndex);
            if (num >= dequeLastNum){
                //这边deque.offer(i)和下面else里的deque.offer(i)其实可以合并，
                // 将if判断条件取反执行else里的逻辑，并最终都if外deque.offer(i)
                deque.offer(i);
            }else {
                while (!deque.isEmpty() && getNumByIndex(deque.peekLast())>num){
                    dequeLastIndex = deque.pollLast();
                    //最终终止边界不好判断的话，可以直接在这里判断-1索引终止
                    if (dequeLastIndex == -1){
                        return max;
                    }
                    dequeLastNum = getNumByIndex(dequeLastIndex);
                    int length = i - deque.peekLast() - 1;
                    int area = dequeLastNum * length;
                    max = Math.max(area,max);
                }
                deque.offer(i);
            }
        }
        return max;
    }

    private int getNumByIndex(int index){
        if (index==arr.length || index==-1){
            return 0;
        }
        return arr[index];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

给你一个正整数组成的数组 nums ，返回 nums 中一个 升序 子数组的最大可能元素和。

子数组是数组中的一个连续数字序列。

已知子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，若对所有 i（l <= i < r），numsi < numsi+1 都成立，则称这一子数组为 升序 子数组。注意，大小为 1 的子数组也视作 升序 子数组。

 

示例 1：

输入：nums = [10,20,30,5,10,50]
输出：65
解释：[5,10,50] 是元素和最大的升序子数组，最大元素和为 65 。

示例 2：

输入：nums = [10,20,30,40,50]
输出：150
解释：[10,20,30,40,50] 是元素和最大的升序子数组，最大元素和为 150 。 

示例 3：

输入：nums = [12,17,15,13,10,11,12]
输出：33
解释：[10,11,12] 是元素和最大的升序子数组，最大元素和为 33 。 

示例 4：

输入：nums = [100,10,1]
输出：100

 

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

\n

题解

简单题，看人家发出来就顺手撸一下看看，没啥特别细节要点和技巧，单向遍历，根据递增特性判断下，是就继续加，不是则从头开始加。然后再遍历的过程中比较下已经得到过的最大值。

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxAscendingSum(int[] nums) {
        int max = nums[0];
        int tmp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i]> nums[i-1]){
                tmp += nums[i];
            }else{
                tmp = nums[i];
            }
            max = Math.max(max,tmp);
        }
        return max;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

返回 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. 1 <= A.length <= 50000
2. -10 ^ 5 <= A[i] <= 10 ^ 5
3. 1 <= K <= 10 ^ 9

\n

题解

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int[] sum = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            if (k <= nums[i]){
                return 1;
            }
            sum[i+1] = nums[i] + sum[i];
        }
        //前缀和数组sum
        int res = Integer.MAX_VALUE;
        Deque<Integer> queue = new LinkedList<>();
        for(int i=0;i<sum.length;i++){
            while(!queue.isEmpty()&&sum[i]<=sum[queue.peekLast()]) {
                queue.pollLast();
            }
            while(!queue.isEmpty()&&sum[i]-sum[queue.peek()]>=k) {
                res = Math.min(res,i-queue.poll());
            }
            queue.add(i);
        }
        return res==Integer.MAX_VALUE?-1:res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)