Skip to content

Commit 84351c3

Browse files
awangdevawangdev
committed
stack
1 parent a85bb1f commit 84351c3

10 files changed

Lines changed: 1162 additions & 648 deletions

‎Java/Expression Expand.java‎

Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
M
2+
1520800825
3+
tags: Divide and Conquer, Stack, DFS
4+
5+
==== 方法1 - Stack
6+
Stack存 [ ] 里面的内容, detect 括号开头结尾: 结尾时process inner string
7+
有很多需要注意的细节才能做对:
8+
- Stack<Object> 也可以用, 每个地方要注意 cast. 存进去的需要是Object: String, Integer
9+
- 几个 type check: instanceof String, Character.isDigit(x), Integer.valueOf(int num)
10+
- 出结果时候, 不能轻易 sb.reverse().toString(): sb.reverse() 翻转了整个连在一起的string, 错.
11+
用另一个Stack<String>作为buffer, 先把stack里面的内容倒出来 (pure), 但是每个item里面顺序不变.
12+
最后再从buffer里面倒进StringBuffer.
13+
14+
==== 方法2 - DFS
15+
与Stack时需要考虑的一些function类似. 特别之处: **检查[ ]的结尾**
16+
因为DFS时候, 括号里的substring会被保留着进入下一个level, 所以我们在base level要keep track of substring.
17+
用int paren 来track 括号的开合, 当paren再次==0的时候 找到closure ']'
18+
19+
```
20+
/*
21+
Given an expression s includes numbers, letters and brackets.
22+
Number represents the number of repetitions inside the brackets(can be a string or another expression)．
23+
Please expand expression to be a string.
24+
*/
25+
26+
/*
27+
Thoughts:
28+
Can DFS. Also, use stack to hold all inner bucket.
29+
In the original string, block of string is separated by #[ ].
30+
Can use stack to hold 2 piece of information:
31+
1. # where the str repeats, and it also marks the start of the string
32+
2. Store each char of the string itself
33+
3. Once flatten the inner str, repeat the str # times and add back to stack
34+
35+
As we iterate over the string
36+
- detect '[' to determine the time to add start marker #.
37+
- detect ']' when it's time to retrieve the # and str, save results
38+
39+
Important: use Stack to hold generic Object!
40+
*/
41+
public class Solution {
42+
/**
43+
* @param s: an expression includes numbers, letters and brackets
44+
* @return: a string
45+
*/
46+
47+
public String expressionExpand(String s) {
48+
if (s == null || s.length() == 0) {
49+
return "";
50+
}
51+
Stack<Object> stack = new Stack<>();
52+
int number = 0;
53+
for (char c : s.toCharArray()) {
54+
if (Character.isDigit(c)) {
55+
number = number * 10 + (c - '0');
56+
} else if (c == '[') {
57+
stack.push(Integer.valueOf(number));
58+
number = 0;
59+
} else if (c == ']') {
60+
String str = popStack(stack);
61+
Integer num = (Integer) stack.pop();
62+
for (int i = 0; i < num; i++) {
63+
stack.push(str);
64+
}
65+
} else {
66+
stack.push(String.valueOf(c));
67+
}
68+
}
69+
70+
return popStack(stack);
71+
}
72+
73+
private String popStack(Stack<Object> stack) {
74+
StringBuffer sb = new StringBuffer();
75+
Stack<String> buffer = new Stack<>();
76+
while (!stack.isEmpty() && (stack.peek() instanceof String)) {
77+
buffer.push((String) stack.pop());
78+
}
79+
80+
while (!buffer.isEmpty()) {
81+
sb.append(buffer.pop());
82+
}
83+
return sb.toString();
84+
}
85+
}
86+
87+
88+
/*
89+
Thoughts:
90+
DFS, process inner string each time.
91+
Use "#[" as detection.
92+
Important:
93+
1. Finding the closure of ']' is tricky: need to track the parentheses
94+
2. Until we find the closure ']', keep track of the un-flatten substring for dfs to use
95+
*/
96+
public class Solution {
97+
/**
98+
* @param s: an expression includes numbers, letters and brackets
99+
* @return: a string
100+
*/
101+
public String expressionExpand(String s) {
102+
if (s == null || s.length() == 0) {
103+
return "";
104+
}
105+
StringBuffer sb = new StringBuffer();
106+
String substring = "";
107+
int number = 0;
108+
int paren = 0; // parentheses tracker
109+
110+
for (int i = 0; i < s.length(); i++) {
111+
char c = s.charAt(i);
112+
if (c == '[') {
113+
if (paren > 0) { // if paren == 0, it indicates the outside 1st '[', no need to record
114+
substring += c;
115+
}
116+
paren++;
117+
} else if (c == ']') {
118+
paren--;
119+
if (paren == 0) {
120+
String innerString = expressionExpand(substring);
121+
for (int num = 0; num < number; num++) {
122+
sb.append(innerString);
123+
}
124+
number = 0;
125+
substring = "";
126+
} else {
127+
substring += c;
128+
}
129+
} else if (Character.isDigit(c)) {
130+
if (paren == 0) {
131+
number = number * 10 + (c - '0');
132+
} else {
133+
substring += c;
134+
}
135+
} else {
136+
if (paren == 0) {
137+
sb.append(String.valueOf(c));
138+
} else {
139+
substring += c;
140+
}
141+
}
142+
}
143+
return sb.toString();
144+
}
145+
}
146+
```

‎Java/Implement Queue using Stacks.java‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,13 @@
11
E
2+
1520797719
3+
tags: Stack, Design
24

5+
==== 双Stack
6+
画图, 知道最后maintain的stack是那个 reverseStack: pop(), peek(), empty() 都在这个stack上, 无需变换.
7+
push()里面做stack和reverseStack的来回倾倒.
8+
相比老的code, 在PUSH里面做倾倒, 更容易读.
9+
10+
==== Previous notes
311
双Stack. 一个是等于是queue，一个是backfillStack.
412
Tricky: 是在pop()和peek()的时候backfill, 并且要等到stack用完再backfill.
513
写一下例子就知道，如果提早backfill，stack.peek()就不是queue的head了.
@@ -19,6 +27,54 @@
1927
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
2028
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
2129
*/
30+
/*
31+
Thoughts:
32+
Use 2 stacks:
33+
Stack: hold items in regular stack order
34+
ReverseStack: hold items in the queue order.
35+
36+
- Add: pure from reverseStack into stack, add item, and pure back into reverseStack.
37+
- Remove: remove from reverseStack
38+
- peek, empty are trivial
39+
*/
40+
class MyQueue {
41+
Stack<Integer> stack;
42+
Stack<Integer> reverseStack;
43+
/** Initialize your data structure here. */
44+
public MyQueue() {
45+
stack = new Stack<>();
46+
reverseStack = new Stack<>();
47+
}
48+
49+
/** Push element x to the back of queue. */
50+
public void push(int x) {
51+
while (!reverseStack.isEmpty()) {
52+
stack.push(pop());
53+
}
54+
stack.push(x);
55+
56+
// Pure back
57+
while (!stack.isEmpty()) {
58+
reverseStack.push(stack.pop());
59+
}
60+
}
61+
62+
/** Removes the element from in front of queue and returns that element. */
63+
public int pop() {
64+
return reverseStack.pop();
65+
}
66+
67+
/** Get the front element. */
68+
public int peek() {
69+
return reverseStack.peek();
70+
}
71+
72+
/** Returns whether the queue is empty. */
73+
public boolean empty() {
74+
return reverseStack.isEmpty();
75+
}
76+
}
77+
2278

2379
/*
2480
Thoughts:

‎Java/Largest Rectangle in Histogram.java‎

Lines changed: 62 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,37 +1,75 @@
1+
H
2+
1520813180
3+
tags: Array, Stack
4+
5+
==== Monotonous Stack
6+
重点是根据找Histogram里面rectangle的性质, 维持一个单调递增的Stack
7+
在loop over indexes的时候:
8+
- 如果高度>= previous peek(), 那么对于那个peek, 就意味着, 往下走, 一直走高嘛, 之前的peek总可以继续抄底
9+
- 什么时候不能抄底了呢? 就是有一个下降趋势的时候
10+
- 这时候并不是calculate所有前面的peek, 而是考虑 大于 current height的之前所有的peek.
11+
- 把这些peek到 current height 前一格的rectangle全部找出来: stack.pop()
12+
- 这个stack.pop()的过程里面, 其实没有算上 current height, 因为需要留到下一轮, 把current index加进stack 再说
13+
- 为什么用stack? 因为需要知道连续递增的peek, stack.peek() O(1), 好用
14+
而其实不用stack, 也可以用其他方式记录所有height, 只不过要 O(n)去找peek不方便
15+
16+
==== 知识点
17+
- 理解monotonous stack 是如何被维护的
18+
- 维护monotonous stack 是题目需要, 而不是stack本身性质, 是一种借助 stack.peek() O(1)的巧妙用法.
19+
20+
21+
```
122
/*
2-
Example
3-
Given height = [2,1,5,6,2,3],
4-
return 10.
23+
LeetCode:
24+
https://leetcode.com/problems/largest-rectangle-in-histogram/description/
525
6-
Tags Expand
7-
Array Stack
26+
Given n non-negative integers representing the histogram's bar height,
27+
where the width of each bar is 1, find the area of largest rectangle in the histogram.
828
9-
Thinking Process:
10-
///TODO: missing thinking process for Largest Rectangle in Histogram
29+
[missing image]
30+
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
1131
12-
*/
32+
[missing image]
33+
The largest rectangle is shown in the shaded area, which has area = 10 unit.
1334
14-
public class Solution {
15-
/**
16-
* @param height: A list of integer
17-
* @return: The area of largest rectangle in the histogram
18-
*/
19-
public int largestRectangleArea(int[] height) {
20-
if (height == null || height.length == 0) {
35+
For example,
36+
Given heights = [2,1,5,6,2,3],
37+
return 10.
38+
*/
39+
40+
/*
41+
Thoughts:
42+
Maintain monotonous stack: whenever seeing a decreasing element, process.
43+
Some characteristics when calculating rectangle in histogram
44+
- You turn to think: I have to loop over all indexes then I know for any specific height, for example, 1, occurs across [0 ~ n].
45+
That's partially true
46+
- We should make be best efforts on calculating: up to certain index, what's maximum we could get.
47+
As we maintain the monotonous ascending stack, stack.peek() element is always the starting point of the rectangle
48+
- [important] Only need to stop and calculate rectangle when seeing a descending element
49+
- It's like, keep climbing the mountain; when it descreases at a point,
50+
trace back to use all previous peeks and form rectangle with current position
51+
*/
52+
class Solution {
53+
public int largestRectangleArea(int[] heights) {
54+
if (heights == null || heights.length == 0) {
2155
return 0;
22-
}
23-
Stack<Integer> stack = new Stack<Integer>();
56+
}
57+
int n = heights.length;
2458
int max = 0;
25-
for (int i = 0; i <= height.length; i++) {
26-
int current = (i == height.length) ? -1 : height[i];
27-
while (!stack.empty() && current <= height[stack.peek()]) {
28-
int h = height[stack.pop()];
29-
int w = stack.empty() ? i : i - stack.peek() - 1;
30-
max = Math.max(max, w * h);
59+
Stack<Integer> stack = new Stack<>(); // Use stack to store the index
60+
for (int i = 0; i <= n; i++) {
61+
int currHeight = i == n ? -1 : heights[i];
62+
// Keep stack monotonous; if not, process && calculate rectangle
63+
while (!stack.isEmpty() && currHeight <= heights[stack.peek()]) {
64+
int currPeekHeight = heights[stack.pop()];
65+
// exclude current position; it'll be calculate in next round.
66+
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
67+
max = Math.max(max, currPeekHeight * width);
3168
}
3269
stack.push(i);
3370
}
71+
3472
return max;
3573
}
3674
}
37-
75+
```

0 commit comments

Comments
 (0)