这里记录刷hot100的思考过程详解，方便后续记忆复习。
题号20
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
具体题解
class Solution {
public boolean isValid(String s) {
Deque<Character> deque=new ArrayDeque<>();
Map<Character,Character> hashmap=new HashMap<>(
Map.of(
'(',')',
'[',']',
'{','}'
)
);
for(int i=0;i<s.length();i++){
if(hashmap.containsKey(s.charAt(i))){
deque.push(s.charAt(i));
}else if(!hashmap.containsKey(s.charAt(i))&&!deque.isEmpty()&&s.charAt(i)==hashmap.get(deque.peek())){
deque.pop();
}
else{
return false;
}
}
return deque.isEmpty();
}
}
思路解析
由题目规则可知，当遍历到右括号时，该符号前一个一定要是对应左括号。因此栈的数据结构特性，左括号压入，右括号取出。使用HashMap匹配右括号对应左括号。如果括号匹配失败或最后栈不为空则返回false。
必会知识
1.栈的初始化以及peek()，pop()，push()等常用函数
2.利用Map.of()初始化HashMap
3.containsKey()与charAt()
题号115
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素val推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
具体题解
class MinStack {
Deque<Integer> stack1;
Deque<Integer> stack2;
public MinStack() {
stack1=new ArrayDeque<>();
stack2=new ArrayDeque<>();
}
public void push(int val) {
stack1.push(val);
if(stack2.isEmpty()||val<=stack2.peek()){
stack2.push(val);
}else{
stack2.push(stack2.peek());
}
}
public void pop() {
stack2.pop();
stack1.pop();
}
public int top() {
return stack1.peek();
}
public int getMin() {
return stack2.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
思路解析
通过两个栈实现，其中一个栈只存储当前最小元素。核心在于push函数的设计。
必会知识
栈的初始化，常用函数等
题号394
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105
具体题解
class Solution {
public String decodeString(String s) {
Deque<Integer> stack1=new ArrayDeque<>();
Deque<String> stack2=new ArrayDeque<>();
StringBuffer ans=new StringBuffer();
int num=0;
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(c=='['){
stack1.push(num);
stack2.push(ans.toString());
ans=new StringBuffer();
num=0;
}else if(c==']'){
StringBuffer tmp=new StringBuffer();
int tmp_num=stack1.pop();
for(int j=0;j<tmp_num;j++){
tmp.append(ans);
}
ans=new StringBuffer(stack2.pop()+tmp);
}else if(c>='0'&&c<='9'){
num=num*10+(c-'0');
}else{
ans.append(c);
}
}
return ans.toString();
}
}
思路解析
核心在于明辨遍历字符串时，对于每个字符应该做什么。遍历过程可划分为以例如3[aas]为单元的多个阶段，而每个阶段需要遍历数字，左括号，字母，右括号。利用StringBuffer类型存储当前遍历阶段最终字符串，利用两个stack栈暂时存储上一阶段的数字和字符串。再划分出4个if来决定每种字符的对应操作。
必会知识
1.StringBuffer的核心函数，append，toString等
题号739
739. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
具体题解
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
Deque<Integer> stack=new ArrayDeque<>();
int length=temperatures.length;
int[] ans=new int[length];
for(int i=0;i<length;i++){
int tmp=temperatures[i];
while(!stack.isEmpty()&&tmp>temperatures[stack.peek()]){
int index=stack.pop();
ans[index]=i-index;
}
stack.push(i);
}
return ans;
}
}
思路解析
通过单调栈实现。这里比较绕的是遍历时的tmp是被比较的对象，如果大于栈顶元素对应温度，则去改变栈顶元素对应ans。
必会知识
单调栈实现模板
for(int i=0;i<length;i++){
int tmp=temperatures[i];
while(!stack.isEmpty()&&tmp>temperatures[stack.peek()]){
int index=stack.pop();
ans[index]=i-index;
}
stack.push(i);
}
题号84
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
具体题解
class Solution {
public int largestRectangleArea(int[] heights) {
int n=heights.length;
int [] left=new int[n];
int [] right=new int[n];
Deque<Integer> mono_stack=new ArrayDeque<>();
Arrays.fill(right,n);
for(int i=0;i<n;i++){
while(!mono_stack.isEmpty()&&heights[mono_stack.peek()]>heights[i]){
right[mono_stack.pop()]=i;
}
left[i]=(mono_stack.isEmpty()?-1:mono_stack.peek());
mono_stack.push(i);
}
int ans=0;
for(int i=0;i<n;i++){
ans=Math.max(ans,(right[i]-left[i]-1)*heights[i]);
}
return ans;
}
}
思路解析
利用单调栈，找以当前柱子高度的最大矩形，并用两个数组存储边界下标（左更小与右更小）。
在决定right时，以栈内元素为主体。在决定left时，以当前遍历下标为主体。
必会知识
1.初始化右数组为n，Arrays.fill(right,n)
2.单调栈写法
