Skip to content

Commit a914f72

Browse files
daachengdaacheng
committed
更新md
更新md
1 parent 5753938 commit a914f72

File tree

4 files changed

+212
-0
lines changed

4 files changed

+212
-0
lines changed

‎leetcode_stack/main.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,3 +2,6 @@
22
1. [有效的括号](有效的括号.md)
33

44
2. [最小栈](最小栈.md)
5+
3. [用队列实现栈](用队列实现栈.md)
6+
4. [用栈实现队列](用栈实现队列.md)
7+
5. [下一个更大元素1](下一个更大元素1.md)

‎leetcode_stack/下一个更大元素1.md‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
## 下一个更大元素1
2+
给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
3+
4+
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
5+
6+
示例：
7+
```python
8+
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
9+
输出: [-1,3,-1]
10+
解释:
11+
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
12+
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
13+
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
14+
```
15+
16+
## 代码
17+
* 先对nums2中每个元素，找到其对应的下一个更大元素，存到字典中
18+
* 再遍历nums1,直接找出答案
19+
20+
#### 如何找到nums2中每个元素对应的下一个更大的元素之间的映射关系
21+
单调栈.
22+
```python
23+
nums2 = [2,3,5,1,0,7,3]
24+
25+
1.
26+
stack = []
27+
2.
28+
stack = [2]
29+
3.
30+
2<3
31+
map_dict = {2:3}
32+
stack = [3]
33+
4.
34+
3<5
35+
map_dict = {2:3, 3:5}
36+
stack = [5]
37+
5.
38+
5>1
39+
map_dict = {2:3, 3:5}
40+
stack = [5, 1]
41+
6.
42+
1>0
43+
map_dict = {2:3, 3:5}
44+
stack = [5, 1, 0]
45+
7.
46+
0<7
47+
map_dict = {2:3, 3:5, 0:7}
48+
stack = [5, 1]
49+
1<7
50+
map_dict = {2:3, 3:5, 0:7, 1:7}
51+
stack = [5]
52+
5<7
53+
map_dict = {2:3, 3:5, 0:7, 1:7, 5:7}
54+
stack = [7]
55+
8.
56+
7>3
57+
map_dict = {2:3, 3:5, 0:7, 1:7, 5:7}
58+
stack = [7, 3]
59+
9.
60+
map_dict = {2:3, 3:5, 0:7, 1:7, 5:7, 7:-1, 3:-1}
61+
```
62+
63+
```python
64+
def nextGreaterElement(nums1, nums2):
65+
map_dict = {}
66+
stack = []
67+
for item in nums2:
68+
if not stack:
69+
stack.append(item)
70+
else:
71+
while stack:
72+
top = stack[-1]
73+
if item > top:
74+
map_dict[top] = item
75+
stack.pop()
76+
else:
77+
stack.append(item)
78+
break
79+
stack.append(item)
80+
for item in stack:
81+
map_dict[item] = -1
82+
83+
res = []
84+
for item in nums1:
85+
res.append(map_dict[item])
86+
return res
87+
```

‎leetcode_stack/用栈实现队列.md‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
## 用栈实现队列
2+
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：
3+
4+
实现 MyQueue 类：
5+
6+
* void push(int x) 将元素 x 推到队列的末尾
7+
* int pop() 从队列的开头移除并返回元素
8+
* int peek() 返回队列开头的元素
9+
* boolean empty() 如果队列为空，返回 true ；否则，返回 false
10+
11+
12+
## 代码
13+
* 用两个列表模拟栈，只能后进先出
14+
* 队列先进先出，入队顺序1,2,3,4， 出队顺序也是1,2,3,4
15+
* 入栈，入栈顺序 1，2,3,4， 出栈顺序4,3,2,1
16+
* 出栈，入栈顺序，4,3,2,1， 出栈顺序1,2,3,4,
17+
* 正好两个栈的顺序结合效果等于队列的顺序
18+
19+
```python
20+
class MyQueue:
21+
22+
def __init__(self):
23+
"""
24+
Initialize your data structure here.
25+
"""
26+
self.stack_in = [] # 入栈
27+
self.stack_out = [] # 出栈
28+
29+
def push(self, x: int) -> None:
30+
"""
31+
Push element x to the back of queue.
32+
"""
33+
self.stack_in.append(x)
34+
35+
def pop(self) -> int:
36+
"""
37+
Removes the element from in front of queue and returns that element.
38+
"""
39+
self.peek()
40+
return self.stack_out.pop()
41+
42+
def peek(self) -> int:
43+
"""
44+
Get the front element.
45+
"""
46+
if not self.stack_out:
47+
self.stack_out = self.stack_in[::-1]
48+
self.stack_in = []
49+
return self.stack_out[-1]
50+
51+
def empty(self) -> bool:
52+
"""
53+
Returns whether the queue is empty.
54+
"""
55+
if self.stack_in or self.stack_out:
56+
return False
57+
return True
58+
59+
```

‎leetcode_stack/用队列实现栈.md‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
## 用队列实现栈
2+
使用队列实现栈的下列操作：
3+
* push(x) -- 元素 x 入栈
4+
* pop() -- 移除栈顶元素
5+
* top() -- 获取栈顶元素
6+
* empty() -- 返回栈是否为空
7+
8+
## 代码
9+
* 队列先进先出
10+
* 栈后进先出
11+
* 一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。
12+
13+
```python
14+
from queue import Queue
15+
16+
class MyStack:
17+
18+
def __init__(self):
19+
"""
20+
Initialize your data structure here.
21+
"""
22+
self.stack = Queue()
23+
self.top_ele = None
24+
25+
26+
def push(self, x: int) -> None:
27+
"""
28+
Push element x onto stack.
29+
"""
30+
self.stack.put(x)
31+
self.top_ele = x
32+
33+
34+
def pop(self) -> int:
35+
"""
36+
Removes the element on top of the stack and returns that element.
37+
"""
38+
size = self.stack.qsize()
39+
while size > 1:
40+
ele = self.stack.get()
41+
self.stack.put(ele)
42+
self.top_ele = ele
43+
size -= 1
44+
result = self.stack.get()
45+
return result
46+
47+
48+
def top(self) -> int:
49+
"""
50+
Get the top element.
51+
"""
52+
return self.top_ele
53+
54+
55+
def empty(self) -> bool:
56+
"""
57+
Returns whether the stack is empty.
58+
"""
59+
if self.stack.qsize():
60+
return False
61+
return True
62+
63+
```

0 commit comments

Comments
 (0)