5.栈（五）

题目汇总：https://leetcode-cn.com/tag/stack/

907. 子数组的最小值之和中等（题解都没看懂）

921. 使括号有效的最少添加中等[✔]

946. 验证栈序列中等[✔]

975. 奇偶跳困难（题解才13，不打算做了）

1003. 检查替换后的词是否有效中等[✔]

1019. 链表中的下一个更大节点中等 [✔]

1021. 删除最外层的括号简单（自己没做明白）

1047. 删除字符串中的所有相邻重复项简单[✔]

1124. 表现良好的最长时间段中等（理解题解，自己复现代码）

907. 子数组的最小值之和中等（题解都没看懂）

给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。
由于答案可能很大，因此返回答案模 10^9 + 7。
示例：
输入：[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。
提示： 1 <= A <= 30000， 1 <= A[i] <= 30000

921. 使括号有效的最少添加中等[✔]

给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：

输入："())"，输出：1
示例 2：
输入："((("，输出：3
示例 3：
输入："()"，输出：0
示例 4：
输入："()))(("，输出：4
提示：

1. S.length <= 1000
2. S 只包含 '(' 和 ')' 字符。
   与 20. 有效的括号类似

思路：

用栈存储未配对的括号，能够配对的元素出栈，最后留在栈中的元素为未能配对的括号。

class Solution {//执行用时：2 ms, 在所有 Java 提交中击败了33.65%的用户，//2020/08/08
    public int minAddToMakeValid(String S) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < S.length(); i++){
            char c = S.charAt(i);
            if(!stack.isEmpty()){
                if(stack.peek() == '(' && c == ')'){//栈顶元素为'('，当前遍历到的是')'
                    stack.pop();//这两个匹配出栈
                }else{
                    stack.push(c);
                }
            }
            else{//栈为空
                 stack.push(c);
            }
        }
       
    return stack.size();
    }
}

946. 验证栈序列中等[✔]

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed 是 popped 的排列。

思路：栈

class Solution {//执行用时：3 ms, 在所有 Java 提交中击败了75.09%的用户,//2020/08/08
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushed.length; i++){
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek() == popped[j]){
                stack.pop();
                j++;
            }
        }
    return stack.isEmpty();
    }
}

1003. 检查替换后的词是否有效中等

给定有效字符串 "abc"。
对于任何有效的字符串 V，我们可以将 V 分成两个部分 X 和 Y，使得 X + Y（X 与 Y 连接）等于 V。（X 或 Y 可以为空。）那么，X + "abc" + Y 也同样是有效的。
例如，如果 S = "abc"，
则有效字符串的示例是："abc"，"aabcbc"，"abcabc"，"abcabcababcc"。
无效字符串的示例是："abccba"，"ab"，"cababc"，"bac"。
如果给定字符串 S 有效，则返回 true；否则，返回 false。
示例 1：
输入："aabcbc"
输出：true
解释：
从有效字符串 "abc" 开始。然后我们可以在 "a" 和 "bc" 之间插入另一个 "abc"，产生 "a" + "abc" + "bc"，即 "aabcbc"。
示例 2：
输入："abcabcababcc"
输出：true
解释：
"abcabcabc" 是有效的，它可以视作在原串后连续插入 "abc"。然后我们可以在最后一个字母之前插入 "abc"，产生 "abcabcab" + "abc" + "c"，即 "abcabcababcc"。
示例 3：
输入："abccba"
输出：false
示例 4：
输入："cababc"
输出：false
提示：

1. 1 <= S.length <= 20000
2. S[i] 为 'a'、'b'、或 'c'

思路：

题目描述没看懂，看了下题解，题目的意思就是说
abc 是有效字符串，在一个有效字符串的任意位置插入abc得到的字符串是有效字符串，abc的顺序是「相对有序」的。
当遇到字符a时,直接入栈
当遇到字符b时，检查栈顶是否为字符a ,如果是将b入栈，如果不是返回false；
当遇到字符c时，检查栈顶是否为字符b,如果是将c入栈,（再将栈顶的cba弹出）如果不是返回false
最后判断栈是否为空即可。

class Solution {//执行用时：19 ms, 在所有 Java 提交中击败了40.76%的用户，//2020/08/08
    public boolean isValid(String S) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < S.length(); i++){
            char ch = S.charAt(i);
            if(ch == 'b' && (stack.isEmpty() || (!stack.isEmpty() && stack.peek() != 'a'))){
                return false;
            }
            else if(ch == 'c' && (stack.isEmpty() || (!stack.isEmpty() && stack.peek() != 'b'))){
                return false;
            }
            else{
                stack.push(ch);
            }
            if(ch == 'c'){
                stack.pop();
                stack.pop();
                stack.pop();
            }
        }
    return stack.isEmpty();
    }
}

1019. 链表中的下一个更大节点中等 [✔]

给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
示例 1：
输入：[2,1,5]
输出：[5,5,0]
示例 2：
输入：[2,7,4,3,5]
输出：[7,0,5,5,0]
提示：

1. 对于链表中的每个节点，1 <= node.val <= 10^9
2. 给定列表的长度在 [0, 10000] 范围内

思路：栈

/栈里面存储的是对应位置的 list 元素及其之后元素中最大的值。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：22 ms, 在所有 Java 提交中击败了74.33%的用户，2020/08/06
    public int[] nextLargerNodes(ListNode head) {
        if(head == null)    return null;
        int size = 0;
        ArrayList<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            size++;
            head = head.next;
        }

        Stack<Integer> stack = new Stack<>();//栈里面存储的是对应位置的 list 元素及其之后元素中最大的值
        int[] result = new int[size];
        for(int i = size - 1; i >= 0; i--){
            while(!stack.isEmpty() && stack.peek() <= list.get(i)){
                stack.pop();
            }
            result[i] = stack.isEmpty() ? 0 : stack.peek();
            stack.push(list.get(i));

        }
    return result;
    }
}

1021. 删除最外层的括号简单

有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。
如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。
示例 1：
输入："(()())(())"
输出："()()()"
解释： 输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
示例 2：
输入："(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
示例 3：
输入："()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。
提示：

1. S.length <= 10000
2. S[i] 为 "(" 或 ")"
3. S 是一个有效括号字符串

思路：

可以通过判断栈是否为空来判断是否找到了一个原语

class Solution {//执行用时：23 ms, 在所有 Java 提交中击败了5.23%的用户
    public String removeOuterParentheses(String S) {
        Stack<Character> stack = new Stack<>();
        String res = "";
        for(int i = 0; i < S.length(); i++){
            char ch = S.charAt(i);
            if(ch == ')'){
                stack.pop();
            }
            if(!stack.isEmpty()){
                res += ch;
            }
            if(ch == '('){
                stack.push('(');
            }
        }
    return res;
    }
}

1047. 删除字符串中的所有相邻重复项简单[✔]

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：

1. 1 <= S.length <= 20000
2. S 仅由小写英文字母组成。

思路：

class Solution {//执行用时：207 ms, 在所有 Java 提交中击败了14.82%的用户，2020/08/08
    public String removeDuplicates(String S) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < S.length(); i++){
            char ch = S.charAt(i);
            if(!stack.isEmpty() && stack.peek() == ch){
                stack.pop();
            }else{
                stack.push(ch);
            }

        }
        String ans = "";
        while(!stack.isEmpty())
            ans = stack.pop() + ans;
        return ans;
       
    }
}

1124. 表现良好的最长时间段中等

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
示例 1：
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。
提示：

• 1 <= hours.length <= 10000
• 0 <= hours[i] <= 16

思路：单调栈（单调递减栈）

以输入hours = [9,9,6,0,6,6,9] 为例：
第一步：用1代表大于8的元素，用-1代表小于等于8的元素,得到一个数组[1,1,-1,-1,-1,-1,1]。题目变为我们需要找到一个子序列，其中1的元素数量严格大于-1的元素数量， 也就是需要找到一个子序列，子序列中所有元素的和大于0。
第二步：计算前缀和 presum = [0, 1, 2, 1, 0, -1, -2, -1]。题目也就是找出前缀和数组 presum 中两个索引 i 和 j，使 j - i 最大，且保证 presum[j] - presum[i] 大于 0。即为求 presum 数组中的一个最长的上坡，与 962. 最大宽度坡是一样的。
维护一个单调递减栈，其中存储 presum 中的元素索引，栈中索引指向的元素严格单调递减，由 presum 数组求得单调栈为 stack = [0, 5, 6]， 其表示元素为 [0, -1, -2]。然后从后往前遍历 presum 数组，如果栈顶索引指向元素小于当前遍历的元素值，就出栈，并更新当前最大宽度。

//2020/08/08，与最大宽度坡那个题本质一样的
class Solution {//执行用时：9 ms, 在所有 Java 提交中击败了90.09%的用户
    public int longestWPI(int[] hours) {
        int[] presum = new int[hours.length + 1];
        for(int i = 1; i <= hours.length; i++){
            presum[i] = presum[i - 1] + (hours[i - 1] > 8 ? 1 : -1);//前缀和数组
        }
        Deque<Integer> stack = new ArrayDeque<>();//单调递减栈
        for(int i = 0; i < presum.length; i++){
            if(stack.isEmpty() || presum[stack.peek()] > presum[i]){
                stack.push(i);
            }
        }
        int res = 0;
        for(int i = presum.length - 1; i >= 0; i--){
            while(!stack.isEmpty() && presum[stack.peek()] < presum[i]){
                int cur = stack.pop();
                res = Math.max(res, i - cur);
            }
        }
    return res;
    }
}