KK's blog

LeetCode 155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• getMin() – Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

题目大意：

设计一个栈，支持在常数时间内push，pop，top，和取最小值。

push(x) – 元素x压入栈
pop() – 弹出栈顶元素
top() – 获取栈顶元素
getMin() – 获取栈中的最小值

解题思路：

这是考察Algorithm和data structure的经典问题。用stack即可实现push，top，pop。难点在于O(1)内实现getMin。看一个例子，
按以下顺序加入stack 5, 3, 6, 8, 2
最小值 5, 3, 3, 3, 2
可以看出来，最小值是动态变化的，所以需要动态处理，由于存储的方式与stack一致，所以可以考虑再用一个stack来存最小值。
如果不用额外stack改用Node，将make_pair(x, curMin)一起压入栈stack>中，额外空间复杂度O(n)。 见算法2。
稍改进空间复杂度，最小值只存变化的值，也就是5,3,2，当最小值变化时再存入最小栈。出栈时候，若出栈元素等于最小栈中的元素，
最小栈的元素也要出栈。

注意事项：

1. 当前最小元素可能相等。相等元素也要入最小栈，如5,3,6,3，最小栈为5,3,3。val <= self.min_stack[-1]一定要取等于。
2. 考虑栈为空时，执行pop和peek的操作。这里存在一个decision point，设计原则与stack的操作一致，也就是暴露出exception。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class MinStack(TestCases):

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        self.stack.append(val)

    def pop(self) -> None:
        val = self.stack.pop()
        if self.min_stack and val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

注意事项：

1. 当前最小元素可能相等。相等元素也要入最小栈，如5,3,6,3，最小栈为5,3,3。x <= minS.peek()一定要取等于。
2. 考虑栈为空时，执行pop和peek的操作。这里存在一个decision point，设计原则与stack的操作一致，也就是暴露出exception。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class MinStack {

	 /** initialize your data structure here. */
    public MinStack() {
        s = new Stack<>();
        minS = new Stack<>();
    }
    
    public void push(int x) {
        s.push(x);
        
        if(minS.isEmpty() || x <= minS.peek())
        	minS.push(x);
    }
    
    public void pop() {
        int top = s.pop();
        if(top == minS.peek())
        	minS.pop();
    }
    
    public int top() {
        return s.peek();
    }
    
    public int getMin() {
        return minS.peek();
    }
    
    Stack<Integer> s;
    Stack<Integer> minS;
}

O(1)空间算法分析(不用看)：

时间复杂度为O(1)，空间复杂度O(n)。

算法2也是可以通过leetcode测试的，虽然空间复杂度比上述差。
存储每个新加值对应的min，更加浪费空间

Follow-up:

如果用O(1)额外空间，怎么改进算法？

先考虑最简单的情况，用一个min来记录当前最小值，它可以满足最小值不需更新的情况，解决了问题的一半：
x表示要加入的值，m表示最小值的变量，y是真正加入栈的值
x 1 5 3
m 1 1 1
y 1 5 3
可以看出无论入栈出栈，最小值均为1.

比较难的是最小值需要更新时，如下一个要加入0，最小值要更新m=0，但0不能入栈，前一个最小值1的信息就丢失了，所以要设计一个计算y方法(push)满足

1. 已知条件：含有前一个最小值的的信息。x1<m0.
2. 设计要求：y<m, 因为最小值不更新的时候y值永远大于等于m，必须区分开来，从而知道怎么pop，也就是还原入栈值（最小值）。y1<m1=x1.
   解决了这个问题就解决了另一半的问题。

以下解释如何推出最小值需要更新时y的计算方式（，以及push和pop的方法：

以下例子解释Push
x 1 5 3 0 6
m 1 1 1 0 0
y 1 5 3 -1 6

以下例子解释Pop
x 6 0 3 5 1
m 0 0 1 1 1
y 6 -1 3 5 1
可以看出真正入栈值可以是原数或者是计算值，取决它与最小值的关系。

注意事项：

1. 当前最小元素可能相等。相等元素不用更新最小值，也就是新值直接入栈。
2. 以上递推式的初始条件为：第一个元素是直接加入栈且等于m，无论何种情况都不需任何计算。push时候注意当栈为空，m值为第一个元素的值。
3. 数据溢出。涉及int的加减乘除法，都要预先将其转化为long，否则会溢出。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class MinStack {
     public MinStack() {
        s = new Stack<>();
    }
    
    public void push(int x) {
    	if (s.isEmpty())
    		m = x;
    	
    	long xx = (long)x;
    	if (x >= m)
    		s.push(xx);
    	else {
    		s.push(2*xx-m);
    		m = x;
    	}
    }
    
    public void pop() {
        long top = s.pop();
        if(top < m)     
        	m = 2*m - top;
    }
    
    public int top() {
        return (int)(s.peek() >= m? s.peek() : m);
    }
    
    public int getMin() { 
        return (int)m;
    }
    
    Stack<Long> s;
    long m = 0;
}

算法分析：

时间复杂度为O(1)，空间复杂度O(1)。

考点:

1. 先不考虑getMin，用什么数据结构实现push, pop, top
2. 暴力法可以实现getMin，怎么实现O(1)。用什么数据结构实现存储min，额外用一个stack
3. 元素可能相等
4. 考虑栈为空时，执行pop和peek的操作

LeetCode

Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

1 <= points.length <= 300 points[i].length == 2
-10<sup>4</sup> <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>4</sup> All the points are unique.

题目大意：

求在同一直线上的点的最大个数

解题思路：

固定一个点，求其与其他点的斜率是否相同，记录在map中。通过同一个点，若斜率相同，肯定在同一直线上。这是几何题。

解题步骤：

N/A

注意事项：

1. 两重循环，外循环为每个点，内循环为该点和其他的点的斜率。斜率可以为无穷大

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12

def maxPoints(self, points: List[List[int]]) -> int:
	res = 0
	for i in range(len(points)):
		slope_to_count = collections.defaultdict(int)
		max_p = 0
		for j in range(i + 1, len(points)):
			slope = (points[j][1] - points[i][1]) / (points[j][0] - points[i][0]) \
				if points[j][0] - points[i][0] != 0 else float('inf') # remember line is y-axis
			slope_to_count[slope] += 1
			max_p = max(max_p, slope_to_count[slope])
		res = max(res, max_p + 1)
	return res

算法分析：

时间复杂度为O(n2)，空间复杂度O(n)

LeetCode

Input: tokens = [“2”,”1”,”+”,”3”,”“]
Output: 9
Explanation: ((2 + 1)  3) = 9

Input: tokens = [“4”,”13”,”5”,”/“,”+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Input: tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,”“,”/“,”“,”17”,”+”,”5”,”+”]
Output: 22
Explanation: ((10  (6 / ((9 + 3)  -11))) + 17) + 5
= ((10  (6 / (12  -11))) + 17) + 5
= ((10  (6 / -132)) + 17) + 5
= ((10  0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

题目大意：

求逆波兰式计算结果

解题思路：

逆波兰式用Stack

解题步骤：

N/A

注意事项：

1. 左右操作数是有区别的，所以stack先出栈的为右操作数，后出栈的为左操作数
2. 最容易错的是向下取整, 题目返回要求整数。所以要除法后取整int(prev / num)。这点和LeetCode 227 Basic Calculator II一样。也是和Java一致，用类型转化来实现，而//是比它小的整数如-2.8就是-3，只在负数是有区别

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def evalRPN(self, tokens: List[str]) -> int:
	stack = []
	for token in tokens:
		if token in '+-*/':
			operand_right = stack.pop() # remember
			operand_left = stack.pop()
			if token == '+':
				stack.append(operand_left + operand_right)
			elif token == '-':
				stack.append(operand_left - operand_right)
			elif token == '*':
				stack.append(operand_left * operand_right)
			else:
				stack.append(int(operand_left / operand_right)) # remember
		else:
			stack.append(int(token))
	return stack[-1]

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

LeetCode

Input: s = “the sky is blue”
Output: “blue is sky the”

Input: s = “  hello world  “
Output: “world hello”
Explanation: Your reversed string should not contain leading or trailing spaces.

Input: s = “a good   example”
Output: “example good a”
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

题目大意：

反转字符串中的单词顺序

解题思路：

N/A

解题步骤：

N/A

注意事项：

1. word不能为空，单词之间可能含多个空格

Python代码：

1
2
3
4

def reverseWords(self, s: str) -> str:
	words = s.split(' ')
	words_without_space = [word for word in words if word]
	return ' '.join(words_without_space[::-1])

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

LeetCode

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

题目大意：

求子数组最大积

解题思路：

类似于LeetCode 053 Maximum Subarray求子数组最大和，用DP。

递归式； dp为以某个数为结尾的最大子数组积，dp2为以某个数为结尾的最小子数组积

1
2

dp[i] = max(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])
dp2[i] = min(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])

解题步骤：

N/A

注意事项：

1. 由于负负得正，所以是多状态DP。需要同时赋值

Python代码：

1
2
3
4
5
6
7
8
9

# dp[i] = max(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])
# dp2[i] = min(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])
def maxProduct(self, nums: List[int]) -> int:
	max_p, min_p, res = 1, 1, float('-inf')
	for n in nums:
		# remember assign same time
		max_p, min_p = max(n, max_p * n, min_p * n), min(n, max_p * n, min_p * n) # 4, -48 | 4, -8, -48
		res = max(res, max_p) # 6
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)