hot100之栈
<h3 id="有效的括号020">有效的括号(020)</h3><p>跳过</p>
<h3 id="最小栈155">最小栈(155)</h3>
<pre><code class="language-java">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();
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>使用双端队列作栈</p>
<p>利用动态规划, 每个栈元素维护自身val和min_val</p>
<h3 id="字符串解码394">字符串解码(394)</h3>
<pre><code class="language-java">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;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>递归调用</p>
<h3 id="每日温度739">每日温度(739)</h3>
<p><strong>栈解法</strong></p>
<pre><code class="language-java">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;
}
}
</code></pre>
<p><strong>跳表解法</strong></p>
<pre><code class="language-java">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;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p><strong>栈解法</strong></p>
<p>栈用于维护<最近><关联>数据</p>
<p>维护栈的单调性就是在维护栈组中的数据的<关联>性, 栈自身的性质可以用于保持<最近>特性</p>
<p><strong>跳表解法</strong></p>
<p>可能也许这是贪心</p>
<h3 id="柱状图中最大矩形084">柱状图中最大矩形(084)</h3>
<pre><code class="language-java">class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int res = 0;
for (int rig = 0; rig <= n; i++){
int h = rig < n ? heights : -1;
while(stack.size() > 1 && h <= heights){
int height = heights;
int lef = stack.peek();
res = Math.max(res, height * (rig - lef - 1));
}
stack.push(rig);
}
return
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>维护栈的单调性, 非单调时弹出数据作max比较</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18938219
頁:
[1]