题目汇总：https://leetcode-cn.com/tag/stack/
385. 迷你语法分析器中等（不做）
394. 字符串解码（不会做）
402. 移掉K位数字中等（看题解可理解）
456. 132模式中等（不做）
496. 下一个更大元素 I简单[✔]
503. 下一个更大元素 II中等[✔]
591. 标签验证器困难（不做）
636. 函数的独占时间中等（不做）
682. 棒球比赛简单[✔]
394. 字符串解码中等
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为:k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像3a或2[4]的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
思路：
class Solution {//执行用时：2 ms, 在所有 Java 提交中击败了55.19%的用户
public String decodeString(String s) {
StringBuilder res = new StringBuilder();
int multi = 0;
LinkedList<Integer> stack_multi = new LinkedList<>();
LinkedList<String> stack_res = new LinkedList<>();
for(Character c : s.toCharArray()) {
if(c == '[') {
stack_multi.addLast(multi);
stack_res.addLast(res.toString());
multi = 0;
res = new StringBuilder();
}
else if(c == ']') {
StringBuilder tmp = new StringBuilder();
int cur_multi = stack_multi.removeLast();
for(int i = 0; i < cur_multi; i++) tmp.append(res);
res = new StringBuilder(stack_res.removeLast() + tmp);
}
else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
else res.append(c);
}
return res.toString();
}
}
402. 移掉K位数字中等
给定一个以字符串表示的非负整数
num，移除这个数中的 k位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例** 3 :**
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。
思路：辅助栈
class Solution {
public String removeKdigits(String num, int k) {
if(k>=num.length()||num.length()==0)
return "0";
Stack<Integer> stack = new Stack<>();
stack.push(num.charAt(0)-'0');
for(int i=1;i<num.length();i++){
while(!stack.isEmpty() && k>0 && stack.peek()>num.charAt(i)-'0'){
stack.pop();
k--;
}
// 如果n!=0，入栈；如果n==0，但是栈不空，入栈
if(num.charAt(i)-'0'!=0 || !stack.isEmpty()){
stack.push(num.charAt(i)-'0');
}
}
//遍历完，但是还没去掉k个数字
while(k>0){
k--;
stack.pop();
}
if(stack.isEmpty())
return "0";
StringBuilder s = new StringBuilder();
while(!stack.isEmpty()){
s.append(stack.pop());
}
return s.reverse().toString();//从后往前添加所以我们要逆序
}
}
496. 下一个更大元素 I简单
给定两个** 没有重复元素** 的数组
nums1和nums2，其中nums1是nums2的子集。找到nums1中每个元素在nums2中的下一个比其大的值。
nums1中数字 x 的下一个更大元素是指 x 在nums2中对应位置的右边的第一个比 **x **大的元素。如果不存在，对应位置输出 -1 。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
思路：单调栈+哈希表
先对 nums2 中的每一个元素，求出其下一个更大的元素。随后对于将这些答案放入哈希映射（HashMap）中，再遍历数组 nums1，并直接找出答案。维护一个单调栈，栈中的元素从栈顶到栈底是单调不降的。
class Solution {//执行用时：4 ms, 在所有 Java 提交中击败了90.74%的用户
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack<Integer> stack = new Stack<>();
HashMap<Integer,Integer> map = new HashMap<>();
int[] res = new int[nums1.length];
for(int num : nums2){
while(!stack.isEmpty() && stack.peek() < num){
map.put(stack.pop(), num);
}
stack.push(num);
}
for(int i=0;i<nums1.length;i++){
res[i] = map.getOrDefault(nums1[i],-1);
}
return res;
}
}
503. 下一个更大元素 II中等
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。
思路：单调栈+HashMap
与 496. 下一个更大元素 I区别在于数组是循环数组，因此复制两倍数组，另外单调栈中存的是数组下标。
class Solution {//执行用时：18 ms, 在所有 Java 提交中击败了36.06%的用户
public int[] nextGreaterElements(int[] nums) {
Stack<Integer> stack = new Stack<>();
HashMap<Integer,Integer> map = new HashMap<>();
int len = nums.length;
int[] res = new int[len];
int[] doubleNums = new int[len * 2];
//复制一份新的数组
for (int i = 0; i < 2; i++) {
for (int j = 0; j < len; j++) {
doubleNums[len * i + j] = nums[j];
}
}
for(int i=0; i < len * 2; i++){
while(!stack.isEmpty() && doubleNums[stack.peek()] < doubleNums[i]){
map.put(stack.pop(), doubleNums[i]);
}
stack.push(i);
}
for(int i=0;i<len;i++){
res[i] = map.getOrDefault(i,-1);
}
return res;
}
}
682. 棒球比赛简单
你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
整数（一轮的得分）：直接表示您在本轮中获得的积分数。
"+"（一轮的得分）：表示本轮获得的得分是前两轮有效回合得分的总和。
"D"（一轮的得分）：表示本轮获得的得分是前一轮有效回合得分的两倍。
"C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效回合的分数是无效的，应该被移除。
每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。
示例 1:
输入: ["5","2","C","D","+"]，输出: 30
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。
思路：辅助栈
保持栈上每个有效回合的值。
class Solution {
public int calPoints(String[] ops) {
Stack<Integer> stack = new Stack<>();
int sum = 0;
for(String s:ops){
//表示您获得的最后一个有效 回合的分数是无效的，应该被移除
if(s.equals("C")){
sum -= stack.peek();
stack.pop();
//表示本轮获得的得分是前一轮有效 回合得分的两倍
}else if(s.equals("D")){
sum += 2 * stack.peek();
stack.push(2*stack.peek());
//表示本轮获得的得分是前两轮有效回合得分的总和
}else if(s.equals("+")){
int top1 = stack.peek() ;
stack.pop() ;
int top2 = stack.peek() ;
sum += top1 + top2 ;
stack.push(top1) ;
stack.push(top1 + top2) ;
}else{//直接表示您在本轮中获得的积分数
sum += Integer.valueOf(s);
stack.push(Integer.valueOf(s));
}
}
return sum;
}
}
