hot100之栈
有效的括号(020)跳过
最小栈(155)
class MinStack {
private final Deque<int[]> stack = new ArrayDeque<>();
public MinStack() {
stack.addLast(new int[]{0, Integer.MAX_VALUE});
}
public void push(int val) {
stack.addLast(new int[]{val, Math.min(stack.peekLast(), val)});
}
public void pop() {
stack.removeLast();
}
public int top() {
return stack.peekLast();
}
public int getMin() {
return stack.peekLast();
}
}
[*]分析
使用双端队列作栈
利用动态规划, 每个栈元素维护自身val和min_val
字符串解码(394)
class Solution {
public String decodeString(String s) {
int idx = 0;
StringBuilder builder = new StringBuilder();
while (idx < s.length()){
// 是字母
if (s.charAt(idx) >= 'a'){
builder.append(s.charAt(idx));
idx++;
continue;
}
idx = appendDupString(idx, s, builder);
//是数字
}
return builder.toString();
}
private int appendDupString(int idx, String s , StringBuilder builder){
int prefix_count = 0;
while(s.charAt(idx) != '['){
prefix_count = prefix_count * 10 + s.charAt(idx) - '0';
idx++;
}
int rig_idx = idx+1;
int nest = 1;
while (nest != 0){
if (s.charAt(rig_idx) == '[') nest++;
else if (s.charAt(rig_idx) == ']') nest--;
rig_idx++;
}
String subString = decodeString(s.substring(idx+1, rig_idx-1));
for (int i = 0; i < prefix_count; i++){
builder.append(subString);
}
return rig_idx;
}
}
[*]分析
递归调用
每日温度(739)
栈解法
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int;
Deque<Integer> stack = new ArrayDeque<>();
for (int i = n-1; i >= 0; i--){
int t = temperatures;
while(!stack.isEmpty() && t >=temperatures){
stack.pop();
}
if (!stack.isEmpty()){
res = stack.peek() - i;
}
stack.push(i);
}
return res;
}
}跳表解法
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int;
for (int i = n-2; i >= 0; i--){
for (int j = i+1; j < n; j += res){
if (temperatures > temperatures){
res = j - i;
break;
}
else if (res == 0){
res = 0;
break;
}
}
}
return res;
}
}
[*]分析
栈解法
栈用于维护数据
维护栈的单调性就是在维护栈组中的数据的性, 栈自身的性质可以用于保持特性
跳表解法
可能也许这是贪心
柱状图中最大矩形(084)
class Solution { public int largestRectangleArea(int[] heights) { int n = heights.length; Deque stack = new ArrayDeque(); stack.push(-1); int res = 0; for (int rig = 0; rig1 && h 谢谢楼主提供！
页:
[1]