【LeetCode Hot100】栈篇
前言
本文用于整理LeetCode Hot100中题目解答，因题目比较简单且更多是为了面试快速写出正确思路，只做简单题意解读和一句话题解方便记忆。但代码会全部给出，方便大家整理代码思路。
20. 有效的括号
一句话题意
验证括号序列有效性。
一句话题解
用双向队列模拟栈，然后验证即可。
class Solution {public boolean isValid(String s) {Deque<Character> q = new LinkedList<>();for(char c:s.toCharArray()){if(c==']'){if(q.size()==0)return false;char cc = q.pollFirst();if(cc=='[')continue;return false;}else if(c==')'){if(q.size()==0)return false;char cc = q.pollFirst();if(cc=='(')continue;return false;}else if(c=='}'){if(q.size()==0)return false;char cc = q.pollFirst();if(cc=='{')continue;return false;}q.addFirst(c);}return q.size() == 0;}
}155. 最小栈
一句话题意
要求实现一个数据结构。
实现 MinStack 类:
-
MinStack()初始化堆栈对象。 -
void push(int val)将元素val推入堆栈。 -
void pop()删除堆栈顶部的元素。 -
int top()获取堆栈顶部的元素。 -
int getMin()获取堆栈中的最小元素。
一句话题解
用两个双向队列，一个模拟栈，一个模拟对应的单调栈，每次往最小值。
class MinStack {Deque<Integer> u;Deque<Integer> umn;public MinStack() {u=new LinkedList<Integer>();umn=new LinkedList<Integer>();}public void push(int val) {u.addFirst(val);if(umn.size()==0)umn.addFirst(val);else umn.addFirst(Math.min(val,umn.peekFirst()));}public void pop() {if(u.size()!=0){u.pollFirst();umn.pollFirst();}}public int top() {return u.peekFirst();}public int getMin() {return umn.peekFirst();}
}394. 字符串解码
一句话题意
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
给定编码规则，问原先的字符串是什么。
一句话题解
栈模拟，注意代码细节。
class Solution {public String decodeString(String s) {Deque<StringBuffer> q = new LinkedList<>();q.addFirst(new StringBuffer("!"));for(char c:s.toCharArray()){if(c>='0'&&c<='9'){char cc=q.peekFirst().charAt(0);if(cc>='0'&&cc<='9')q.addFirst(q.pollFirst().append(c));else q.addFirst(new StringBuffer().append(c));}else if(c=='['){q.addFirst(new StringBuffer().append(c));}else if(c>='a'&&c<='z'){char cc=q.peekFirst().charAt(0);if(cc>='a'&&cc<='z'||cc=='!'){q.addFirst(q.pollFirst().append(c));}else{q.addFirst(new StringBuffer().append(c));}}else if(c==']'){StringBuffer s1=q.pollFirst();StringBuffer res=new StringBuffer("");q.pollFirst();StringBuffer num=q.pollFirst();int len=num.length();for(int i=0;i<Long.valueOf(num.toString());i++){res.append(s1);}if(q.peekFirst().charAt(0)!='[')q.addFirst(q.pollFirst().append(res));elseq.addFirst(res);}}return q.pollFirst().toString().substring(1);}
}739. 每日温度
一句话题意
求序列后面比当前天温度高的最近的距离。
一句话题解
单调递减栈。
class Solution {public int[] dailyTemperatures(int[] temperatures) {Deque<Integer> q = new LinkedList<>();int[] ans = new int[temperatures.length];Arrays.fill(ans,0);for(int i=0;i<temperatures.length;i++){if(q.size()==0||temperatures[q.peek()]>temperatures[i]){q.push(i);}else{while(q.size()>0&&temperatures[q.peek()]<temperatures[i]){ans[q.peek()]=i-q.poll();}q.push(i);}}return ans;}
}84. 柱状图中最大的矩形
一句话题意
给定一个竖状图，求矩形最大面积。
一句话题解
单调栈，设定一个单调递增的单调栈，然后每次扔值的时候，如果比前一个大正常往栈里扔，如果小的话就弹出栈内元素。且我们可以知道，当栈内某个元素作为高度，他后面的元素对于他来说都是有贡献的，我们只需要把这个算出来即可。
class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;int ans = 0;Deque<Integer> q = new LinkedList<>();q.addFirst(-1);for (int i = 0; i <= n; i++) {int h;if(i==n) h=-1;else h=heights[i];while (q.size() > 1 && heights[q.peekFirst()] >= h) {int hh = heights[q.pollFirst()];int len = i - q.peekFirst() - 1;ans=Math.max(ans, hh * len);}q.addFirst(i);}return ans;}
}