
class Solution {
    public boolean isValid(String s) {
      //当字符串的长度为奇数时，返回false
      if((s.length())%2==1){
        return false;
      }
      Stack<Character> stack=new Stack<Character>();
      char[] ArrayStr=s.toCharArray();
      //遍历数组内所有元素
      for(int i=0;i<ArrayStr.length;i++){
        char c=ArrayStr[i];
        if(c=='(' || c=='{' || c=='['){
            stack.push(c);
        }else{
            //当要加入右括号时，栈中为空，则直接不匹配
            if(stack.isEmpty()){
                return false;
            }
 
            char top=stack.peek();
            if( (top=='(' && c==')') || (top=='{' && c=='}') || (top=='[' && c==']')){
                stack.pop();
            }else{
                return false;
            }
        }
      }
      return stack.isEmpty();
    }
}

2.最小栈（ LeetCode 155 ）

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.


class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
 
    public MinStack() {
        minStack = new Stack<>();
        stack = new Stack<>();
    }
 
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
 
    public void pop() {
        if (stack.isEmpty()) return;
        int val = stack.pop();
        if (!minStack.isEmpty() && val == minStack.peek()) {
            minStack.pop();
        }
    }
 
    public int top() {
        return stack.peek();
    }
 
    public int getMin() {
        return minStack.peek();
    }
}

3.接雨水（ LeetCode 42 ）

给定 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


class Solution {
    public int trap(int[] height) {
 
        // 只有两根柱子，必然无法形成一个凹槽，那么水的面积就是 0
        if (height.length <= 2) return 0; 
 
        // 构建一个栈，用来存储对应的柱子的下标
        // 注意：stack 存储的是下标而非高度
        Stack<Integer> stack = new Stack<>();
 
        // 一开始水的面积是 0
        int result = 0;
        
        // 从头开始遍历整个数组
        for (int i = 0; i < height.length; i++) {
            // 如果栈为空，那么直接把当前索引加入到栈中
            if(stack.isEmpty()){
                // 把当前索引加入到栈中
                stack.push(i);
 
  // 否则的话，栈里面是有值的，我们需要去判断此时的元素、栈顶元素、栈顶之前的元素能否形成一个凹槽
             // 情况一：此时的元素小于栈顶元素，凹槽的右侧不存在，无法形成凹槽
            }else if (height[i] < height[stack.peek()]) {    
                // 把当前索引加入到栈中
                stack.push(i);
               
               // 情况二：此时的元素等于栈顶元素，也是无法形成凹槽
            } if (height[i] == height[stack.peek()]) {
 
                // 把当前索引加入到栈中
                stack.push(i);
 
               // 情况三：此时的的元素大于栈顶元素，有可能形成凹槽
               // 注意是有可能形成，因为比如栈中的元素是 2 、2 ，此时的元素是 3，那么是无法形成凹槽的
            } else {    
 
         // 由于栈中有可能存在多个元素，移除栈顶元素之后，剩下的元素和此时的元素也有可能形成凹槽
                // 因此，我们需要不断的比较此时的元素和栈顶元素
                // 此时的元素依旧大于栈顶元素时，我们去计算此时的凹槽面积
                // 借助 while 循环来实现这个操作
                while (!stack.empty() && height[i] > height[stack.peek()]) {
 
                  // 1、获取栈顶的下标，bottom 为凹槽的底部位置
                    int bottom = stack.peek();
 
                  // 将栈顶元素推出，去判断栈顶之前的元素是否存在，即凹槽的左侧是否存在
                    stack.pop();
 
                    // 2、如果栈不为空，即栈中有元素，即凹槽的左侧存在
                    if (!stack.empty()) {
 
                    // 凹槽左侧的高度 height[stack.peek() 和 凹槽右侧的高度 height[i] 
                    // 这两者的最小值减去凹槽底部的高度就是凹槽的高度  
                     int h = Math.min(height[stack.peek()], height[i]) - height[bottom];
                       
                  // 凹槽的宽度等于凹槽右侧的下标值 i 减去凹槽左侧的下标值 stack.peek 再减去 1
                        int w = i - stack.peek() - 1; 
 
                        // 将计算的结果累加到最终的结果上去
                        result += h * w;
                    }
                }
 
                // 栈中和此时的元素可以形成栈的情况在上述 while 循环中都已经判断了
                // 那么，此时栈中的元素必然不可能大于此时的元素，所以可以把此时的元素添加到栈中
                stack.push(i);
            }
        }
 
        // 最后返回结果即可
        return result;
    }
}

4.逆波兰表达式求值（LeetCode 150）

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6


class Solution {
    public int evalRPN(String[] tokens) {
        // 使用一个栈存储操作数，从左到右遍历逆波兰表达式
        Stack<Integer> result = new Stack<>();
 
        // 对于一个表达式来说，由两个操作数和一个运算符构成
        // 比如加法：① ＋ ②
        // 比如减法：① -  ②
        // 比如乘法：① *  ②
        // 比如除法：① /  ②
 
        // 先出栈的是右操作数，后出栈的是左操作数
 
        // 先出栈的是右操作数
        int rightNum;
 
        // 后出栈的是左操作数
        int leftNum;
 
        // 一个表达式的计算结果
        int ans;
 
        // 遍历字符串数组
        for(String token : tokens){
 
            // 如果是 + 
            if("+".equals(token)){
 
                // 先出栈的是右操作数
                rightNum = result.pop();
 
                // 后出栈的是左操作数
                leftNum = result.pop();
 
                // 计算结果
                ans = leftNum + rightNum;
 
            // 如果是 - 
            }else if("-".equals(token)){
 
                // 先出栈的是右操作数
                rightNum = result.pop();
 
                // 后出栈的是左操作数
                leftNum = result.pop();
 
                // 计算结果
                ans = leftNum - rightNum;    
 
            // 如果是 *
            }else if("*".equals(token)){
 
                // 先出栈的是右操作数
                rightNum = result.pop();
 
                // 后出栈的是左操作数
                leftNum = result.pop();
 
                // 计算结果
                ans = leftNum * rightNum; 
 
            // 如果是 /
            }else if("/".equals(token)){
 
                // 先出栈的是右操作数
                rightNum = result.pop();
 
                // 后出栈的是左操作数
                leftNum = result.pop();
 
                // 计算结果
                ans = leftNum / rightNum; 
 
            // 如果是非运算符
            }else{
                
                // 转换为数字
                ans = Integer.valueOf(token);
                
            }
 
            // 存储结果
            result.push(ans);
 
        }
 
        // 返回栈顶元素
        return result.pop();
        
    }
}

5.柱状图中最大的矩形（LeetCode 84）

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

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

示例 1:

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


class Solution {
    public int largestRectangleArea(int[] heights) {
 
        // 初始化最终结果为0
        int res = 0;
 
        // 使用单调栈
        Stack<Integer> stack = new Stack<>();
 
        // 将给定的原数组左右各添加一个元素0，方便处理
        int[] newHeights = new int[heights.length + 2];
 
        // 左边界为 0 
        newHeights[0] = 0;
 
        // 右边界边界为 0 
        newHeights[newHeights.length-1] = 0;
 
        // 其余不变
        for (int i = 1; i < heights.length + 1; i++) {
            newHeights[i] = heights[i - 1];
        }
    
       // 整体思路：
       // 对于一个高度，如果能得到向左和向右的边界
       // 那么就能对每个高度求一次面积
       // 遍历所有高度，即可得出最大面积
      
        // 开始遍历
        for (int i = 0; i < newHeights.length; i++) {
            // 如果栈不为空且当前考察的元素值小于栈顶元素值，
            // 则表示以栈顶元素值为高的矩形面积可以确定
            while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                // 弹出栈顶元素
                int cur = stack.pop();
                // 获取栈顶元素对应的高
                int curHeight = newHeights[cur];
 
                // 栈顶元素弹出后，新的栈顶元素就是其左侧边界
                int leftIndex = stack.peek();
                // 右侧边界是当前考察的索引
                int rightIndex = i;
                // 计算矩形宽度
                int curWidth = rightIndex - leftIndex - 1;
 
                // 计算面积
                res = Math.max(res, curWidth * curHeight);
            }
            
            // 当前考察索引入栈
            stack.push(i);
        }
 
        // 返回结果
        return res;
    }
 
}

6.滑动窗口最大值（ LeetCode 239 ）

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]


class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 边界情况
        if(nums.length == 0 || k == 0){
            return new int[0];
        }
        // 构建双端队列
        Deque<Integer> deque = new LinkedList<>();
        // 构建存储最大值的数组
        int[] res = new int[nums.length - k + 1];
        // 一开始滑动窗口不包含 K 个元素，不是合格的滑动窗口
        for(int i = 0; i < k; i++) {
            // 在滑动过程中，维护好 deque，确保它是单调递减队列
 
            // 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
            // 直到考察元素可以放入到队列中
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }
 
            // 考察元素可以放入到队列中
            deque.addLast(nums[i]);
        }
        // 这个时候，滑动窗口刚刚好有 k 个元素，是合格的滑动窗口，那么最大值就是队列中的队首元素
        res[0] = deque.peekFirst();
 
 
        // 现在让滑动窗口滑动
        for(int i = k; i < nums.length; i++) {
            // 滑动窗口已经装满了元素，向右移动会把窗口最左边的元素抛弃
            // i - k 为滑动窗口的最左边
            // 如果队列的队首元素和窗口最左边的元素相等，需要将队首元素抛出
            if(deque.peekFirst() == nums[i - k]){
                deque.removeFirst();
            }
                
 
            // 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
            // 直到考察元素可以放入到队列中
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }
               
            // 考察元素可以放入到队列中
            deque.addLast(nums[i]);
            // 此时，结果数组的值就是队列的队首元素
            res[i - k + 1] = deque.peekFirst();
        }
 
        // 最后返回 res
        return res;
    }
}

7.无重复字符的最长子串（LeetCode 3）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题：滑动窗口+哈希表

使用哈希表的作用：

快速查找：哈希表通常允许在平均 O(1) 时间复杂度内进行查找、插入和删除操作。
键值映射：它通过哈希函数将键映射到表中的位置，支持根据键快速获取相关联的值。
去重：可以用于存储唯一的元素，防止重复值出现。


class Solution {
    public int lengthOfLongestSubstring(String s) {
        //定义记录最大长度的变量
        int maxLong=0;
        //涉及到去重，使用hash表
        HashSet<Character> hash=new HashSet<Character>();
 
        //设置滑动窗口的起始和结束
        int start=0;
        int end=0;
        for(end=0;end<s.length();end++){
            while(hash.contains(s.charAt(end))){
                hash.remove(s.charAt(start));
                start++;
            }
            hash.add(s.charAt(end));
            maxLong=Math.max(maxLong,end-start+1);
        }
        return maxLong;
    }
}

8.删除子数组的最大得分（LeetCode 1695）

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的得分就是子数组各元素之和。

返回 只删除一个 子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]

和上题基本思路一致，只是多了一步计算哈希表中的和。


class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        //构造哈希表存放不同的元素
        HashSet<Integer> hash=new HashSet<Integer>();
        //记录得分
        int sum=0;
        //记录最大得分
        int largest=0;
        //定义滑动窗口的起始和末尾
        int start=0;
        int end=0;
        //开始移动滑动窗口
        for(end=0;end<nums.length;end++){
            while(hash.contains(nums[end])){
                hash.remove(nums[start]);
                sum-=nums[start];
                start++;
            }
            hash.add(nums[end]);
            sum+=nums[end];
            //最大得分
            largest=Math.max(largest,sum);
        }
        return largest;
    }
}

9.找到字符串中所有字母异位词（LeetCode 438）

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。


class Solution {
    public List<Integer> findAnagrams(String s, String p) {
    //构造存放结果的List
    List<Integer> result=new ArrayList();
 
    //need[]存放pz中所有字母出现的频次
    int[] need=new int[26];
    for(char ch:p.toCharArray()){
        need[ch-'a']++;
    }
 
    //定义数组windows[]存放滑动窗口的字母频次
    int[] windows=new int[26];
    //定义滑动窗口
    int start=0;
    int end=0;
    for(end=0;end<s.length();end++){
        //end指的数
        char cur=s.charAt(end);
 
        //end指向的字母，windows[]中的频次加一
        windows[cur-'a']++;
 
        //添加后比较needs[]和windows[]是否相同，相同将start记录到result中
        if(isSame(need,windows)){
            result.add(start);
        }
 
        //滑动窗口的长度超出p的长度后，需要将start的字母频次减一，在将start往后移动
        if(end>=p.length()-1){
            char ch=s.charAt(start);
            windows[ch-'a']--;
            start++;
        }
    }
    return result;
    }
 
 
    public boolean isSame(int[]a,int[]b){
        for(int i=0;i<a.length;i++){
           if( a[i]!=b[i]){
            return false;
           }
        }
        return true;
    }
}

10.总结

1.栈的实现 Stack<xxx> stack = new Stack<>();常用方法push()、pop()、peek()

2.队列的实现 Queue<xxx> queue = new LinkedList<>();add()、poll()、peek()、removeLast()、addFirst()、peekFirst()...

3.递增栈和递减栈来解决特殊问题（较难）

4.选择使用数组或者哈希表存储：数组连续（比如上面的26个字母）内存简单、哈希表不连续HashSet保证元素的唯一性，支持高效的插入、删除和查找操作、但存储和处理的开销较大。

5.滑动窗口和哈希表的结合可以有效地解决许多涉及子数组或子字符串的问题

滑动窗口技巧

窗口大小:
- 固定大小窗口：窗口的大小在整个过程保持不变，常用于寻找具有特定长度的子数组或子字符串。例如，9.找到字符串中所有字母异位词、6.滑动窗口最大值
- 可变大小窗口：窗口大小根据条件动态调整，常用于找到符合特定条件的最小子数组或子字符串。例如，7.无重复字符的最长子串、8.删除子数组的最大得分
双指针技术:
- 使用两个指针（通常是左指针和右指针）来表示当前的窗口范围，右指针向右移动以扩大窗口，左指针向右移动以缩小窗口。
窗口条件:
- 需要维护窗口中的某些信息（如计数、和、最大值等），并根据条件调整窗口大小

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/996445