Skip to content

Commit 768a893

Browse files
fishercoder1534fishercoder1534
committed
add a solution for 716
1 parent 4c640c0 commit 768a893

File tree

2 files changed

+136
-73
lines changed

2 files changed

+136
-73
lines changed

‎src/main/java/com/fishercoder/solutions/_716.java

+58
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,9 @@
11
package com.fishercoder.solutions;
22

33
import java.util.ArrayList;
4+
import java.util.Deque;
45
import java.util.Iterator;
6+
import java.util.LinkedList;
57
import java.util.List;
68
import java.util.Stack;
79
import java.util.TreeMap;
@@ -191,4 +193,60 @@ public int popMax() {
191193
}
192194
}
193195
}
196+
197+
public static class Solution3 {
198+
/**
199+
* My completely original solution on 10/25/2021.
200+
* popMax() takes O(n) time, all other operations take O(1) time.
201+
*/
202+
203+
public static class MaxStack {
204+
205+
Deque<int[]> stack;
206+
Deque<int[]> tmp;
207+
208+
public MaxStack() {
209+
stack = new LinkedList<>();
210+
tmp = new LinkedList<>();
211+
}
212+
213+
public void push(int x) {
214+
if (stack.isEmpty()) {
215+
stack.addLast(new int[]{x, x});
216+
} else {
217+
int[] last = stack.peekLast();
218+
stack.addLast(new int[]{x, Math.max(last[1], x)});
219+
}
220+
}
221+
222+
public int pop() {
223+
return stack.pollLast()[0];
224+
}
225+
226+
public int top() {
227+
return stack.peekLast()[0];
228+
}
229+
230+
public int peekMax() {
231+
return stack.peekLast()[1];
232+
}
233+
234+
public int popMax() {
235+
tmp.clear();
236+
while (stack.peekLast()[0] != stack.peekLast()[1]) {
237+
tmp.addLast(stack.pollLast());
238+
}
239+
int[] max = stack.pollLast();
240+
while (!tmp.isEmpty()) {
241+
int[] curr = tmp.pollLast();
242+
if (!stack.isEmpty()) {
243+
stack.addLast(new int[]{curr[0], Math.max(curr[0], stack.peekLast()[1])});
244+
} else {
245+
stack.addLast(new int[]{curr[0], curr[0]});
246+
}
247+
}
248+
return max[0];
249+
}
250+
}
251+
}
194252
}

‎src/test/java/com/fishercoder/_716Test.java

+78-73
Original file line numberDiff line numberDiff line change
@@ -7,84 +7,89 @@
77
import static org.junit.Assert.assertEquals;
88

99
public class _716Test {
10-
private static _716.Solution1.MaxStack maxStackSolution1;
11-
private static _716.Solution2.MaxStack maxStackSolution2;
10+
private static _716.Solution1.MaxStack maxStackSolution1;
11+
private static _716.Solution2.MaxStack maxStackSolution2;
12+
private static _716.Solution3.MaxStack maxStackSolution3;
1213

13-
@Before
14-
public void setup() {
15-
maxStackSolution1 = new _716.Solution1.MaxStack();
16-
maxStackSolution2 = new _716.Solution2.MaxStack();
17-
}
14+
@Before
15+
public void setup() {
16+
maxStackSolution1 = new _716.Solution1.MaxStack();
17+
maxStackSolution2 = new _716.Solution2.MaxStack();
18+
maxStackSolution3 = new _716.Solution3.MaxStack();
19+
}
1820

19-
@Test
20-
public void test1() {
21-
maxStackSolution1.push(5);
22-
assertEquals(5, maxStackSolution1.peekMax());
23-
assertEquals(5, maxStackSolution1.popMax());
24-
}
21+
@Test
22+
public void test1() {
23+
maxStackSolution1.push(5);
24+
assertEquals(5, maxStackSolution1.peekMax());
25+
maxStackSolution2.push(5);
26+
assertEquals(5, maxStackSolution2.popMax());
27+
maxStackSolution3.push(5);
28+
assertEquals(5, maxStackSolution3.popMax());
29+
}
2530

26-
@Test
27-
public void test2() {
28-
maxStackSolution1.push(5);
29-
maxStackSolution1.push(1);
30-
assertEquals(5, maxStackSolution1.popMax());
31-
assertEquals(1, maxStackSolution1.peekMax());
32-
}
31+
@Test
32+
public void test2() {
33+
maxStackSolution1.push(5);
34+
maxStackSolution1.push(1);
35+
assertEquals(5, maxStackSolution1.popMax());
36+
assertEquals(1, maxStackSolution1.peekMax());
37+
}
3338

34-
@Test
35-
public void test3() {
36-
maxStackSolution1.push(74);
37-
assertEquals(74, maxStackSolution1.popMax());
38-
maxStackSolution1.push(89);
39-
maxStackSolution1.push(67);
40-
assertEquals(89, maxStackSolution1.popMax());
41-
assertEquals(67, maxStackSolution1.pop());
42-
maxStackSolution1.push(61);
43-
maxStackSolution1.push(-77);
44-
assertEquals(61, maxStackSolution1.peekMax());
45-
assertEquals(61, maxStackSolution1.popMax());
46-
maxStackSolution1.push(81);
47-
assertEquals(81, maxStackSolution1.peekMax());
48-
assertEquals(81, maxStackSolution1.popMax());
49-
maxStackSolution1.push(81);
50-
assertEquals(81, maxStackSolution1.pop());
51-
maxStackSolution1.push(-71);
52-
maxStackSolution1.push(32);
53-
}
39+
@Test
40+
public void test3() {
41+
maxStackSolution1.push(74);
42+
assertEquals(74, maxStackSolution1.popMax());
43+
maxStackSolution1.push(89);
44+
maxStackSolution1.push(67);
45+
assertEquals(89, maxStackSolution1.popMax());
46+
assertEquals(67, maxStackSolution1.pop());
47+
maxStackSolution1.push(61);
48+
maxStackSolution1.push(-77);
49+
assertEquals(61, maxStackSolution1.peekMax());
50+
assertEquals(61, maxStackSolution1.popMax());
51+
maxStackSolution1.push(81);
52+
assertEquals(81, maxStackSolution1.peekMax());
53+
assertEquals(81, maxStackSolution1.popMax());
54+
maxStackSolution1.push(81);
55+
assertEquals(81, maxStackSolution1.pop());
56+
maxStackSolution1.push(-71);
57+
maxStackSolution1.push(32);
58+
}
5459

55-
@Test
56-
public void test4() {
57-
maxStackSolution2.push(5);
58-
assertEquals(5, maxStackSolution2.peekMax());
59-
assertEquals(5, maxStackSolution2.popMax());
60-
}
60+
@Test
61+
public void test4() {
62+
maxStackSolution2.push(5);
63+
assertEquals(5, maxStackSolution2.peekMax());
64+
assertEquals(5, maxStackSolution2.popMax());
65+
}
6166

62-
@Test
63-
public void test5() {
64-
maxStackSolution2.push(5);
65-
maxStackSolution2.push(1);
66-
assertEquals(5, maxStackSolution2.popMax());
67-
assertEquals(1, maxStackSolution2.peekMax());
68-
}
67+
@Test
68+
public void test5() {
69+
maxStackSolution2.push(5);
70+
maxStackSolution2.push(1);
71+
assertEquals(5, maxStackSolution2.popMax());
72+
assertEquals(1, maxStackSolution2.peekMax());
73+
}
6974

70-
@Test
71-
public void test6() {
72-
maxStackSolution2.push(74);
73-
assertEquals(74, maxStackSolution2.popMax());
74-
maxStackSolution2.push(89);
75-
maxStackSolution2.push(67);
76-
assertEquals(89, maxStackSolution2.popMax());
77-
assertEquals(67, maxStackSolution2.pop());
78-
maxStackSolution2.push(61);
79-
maxStackSolution2.push(-77);
80-
assertEquals(61, maxStackSolution2.peekMax());
81-
assertEquals(61, maxStackSolution2.popMax());
82-
maxStackSolution2.push(81);
83-
assertEquals(81, maxStackSolution2.peekMax());
84-
assertEquals(81, maxStackSolution2.popMax());
85-
maxStackSolution2.push(81);
86-
assertEquals(81, maxStackSolution2.pop());
87-
maxStackSolution2.push(-71);
88-
maxStackSolution2.push(32);
89-
}
75+
@Test
76+
public void test6() {
77+
maxStackSolution2.push(74);
78+
assertEquals(74, maxStackSolution2.popMax());
79+
maxStackSolution2.push(89);
80+
maxStackSolution2.push(67);
81+
assertEquals(89, maxStackSolution2.popMax());
82+
assertEquals(67, maxStackSolution2.pop());
83+
maxStackSolution2.push(61);
84+
maxStackSolution2.push(-77);
85+
assertEquals(61, maxStackSolution2.peekMax());
86+
assertEquals(61, maxStackSolution2.popMax());
87+
maxStackSolution2.push(81);
88+
assertEquals(81, maxStackSolution2.peekMax());
89+
assertEquals(81, maxStackSolution2.popMax());
90+
maxStackSolution2.push(81);
91+
assertEquals(81, maxStackSolution2.pop());
92+
maxStackSolution2.push(-71);
93+
maxStackSolution2.push(32);
94+
}
9095
}

0 commit comments

Comments
 (0)