CONTENTS
LeetCode 151. 反转字符串中的单词（中等）
【题目描述】
给你一个字符串 s，请你反转字符串中单词的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。
注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
【示例 1】
输入：s = "the sky is blue"
输出："blue is sky the"
【示例 2】
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
【示例 3】
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
【提示】
1 < = s . l e n g t h < = 1 0 4 1 <= s.length <= 10^4 1<=s.length<=104
s 包含英文大小写字母、数字和空格 ' '
s 中至少存在一个单词
进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O ( 1 ) O(1) O(1) 额外空间复杂度的原地解法。
【分析】
本题的思路也挺具有跳跃性，我们可以分解为以下两步操作：
- 翻转整个字符串：例如
the sky is blue -> eulb si yks eht； - 翻转每个单词：例如
eulb si yks eht -> blue is sky the。
这两个操作是互相独立的，也可以先翻转每个单词然后再翻转整个字符串，这样代码写起来更方便一点，翻转的时候可以直接使用 reverse() 函数也可以用双指针实现。
【代码】
class Solution {
public:
string reverseWords(string s) {
int n = 0; // 过滤无效空格后的字符串长度
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') continue;
int j = i;
while (j < s.size() && s[j] != ' ') s[n++] = s[j++];
reverse(s.begin() + n - (j - i), s.begin() + n); // 将单词翻转
s[n++] = ' '; // 末尾统一先加上空格
i = j;
}
n--; // 去掉最后一个空格
for (int l = 0, r = n - 1; l < r; l++, r--) swap(s[l], s[r]); // 双指针翻转整个字符串
s.erase(s.begin() + n, s.end()); // 删去无效的部分
return s;
}
};
LeetCode 152. 乘积最大子数组（中等）
【题目描述】
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32 位整数。
【示例 1】
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
【示例 2】
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
【示例 3】
输入: nums = [-2,3,-4]
输出: 24
解释: 子数组 [-2,3,-4] 有最大乘积 24。
【提示】
1 < = n u m s . l e n g t h < = 2 ∗ 1 0 4 1 <= nums.length <= 2 * 10^4 1<=nums.length<=2∗104
10 < = n u m s [ i ] < = 10 10 <= nums[i] <= 10 10<=nums[i]<=10
nums 的任何子数组的乘积都保证是一个 32 位整数
【分析】
- 状态表示： f [ i ] f[i] f[i] 表示以
nums[i]结尾的连续子区间的乘积最大值， g [ i ] g[i] g[i] 表示以nums[i]结尾的连续子区间的乘积最小值。 - 状态计算：对于以
nums[i]结尾的连续子区间，分以下几种情况：- 区间中只有
nums[i]：区间乘积的最大值与最小值都等于自身，即f[i] = g[i] = nums[i]。 - 区间中包含以
nums[i - 1]结尾的某个连续子区间：- 若
nums[i]大于 0：区间乘积的最大值应该是以nums[i - 1]结尾的连续子区间的乘积最大值再乘上自身，即f[i] = f[i - 1] * nums[i]；区间乘积的最小值应该是以nums[i - 1]结尾的连续子区间的乘积最小值再乘上自身，即g[i] = g[i - 1] * nums[i]。 - 若
nums[i]小于 0：区间乘积的最大值应该是以nums[i - 1]结尾的连续子区间的乘积最小值再乘上自身，即f[i] = g[i - 1] * nums[i]；区间乘积的最小值应该是以nums[i - 1]结尾的连续子区间的乘积最大值再乘上自身，即g[i] = f[i - 1] * nums[i]。 - 若
nums[i]等于 0：区间乘积无论如何都是 0，且这种情况可以算在区间只有nums[i]的情况中，因此也已经包含在内了。
- 若
- 区间中只有
由于 i i i 的状态只依赖于 i − 1 i - 1 i−1，因此可以只用一个变量表示状态，这样空间复杂度就为 O ( 1 ) O(1) O(1)，此外通过观察可以发现 f f f 最终一定就是在 nums[i]、f[i - 1] * nums[i]、g[i - 1] * nums[i] 这三种情况中取最大值，同理 g g g 也是，因此代码可以直接写在一起。
【代码】
【原始版本】
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
vector<int> f(n), g(n);
f[0] = nums[0], g[0] = nums[0];
int res = nums[0];
for (int i = 1; i < n; i++) {
f[i] = g[i] = nums[i]; // 区间只有 nums[i] 的情况
if (nums[i] > 0) f[i] = max(f[i], f[i - 1] * nums[i]), g[i] = min(g[i], g[i - 1] * nums[i]);
else f[i] = max(f[i], g[i - 1] * nums[i]), g[i] = min(g[i], f[i - 1] * nums[i]);
res = max(res, f[i]);
}
return res;
}
};
【空间优化版】
class Solution {
public:
int maxProduct(vector<int>& nums) {
int f = nums[0], g = nums[0], res = nums[0];
for (int i = 1; i < nums.size(); i++) {
int tf = f; // 更新 g 的时候 f 已经更新了，因此开个临时变量存一下 f
f = max(nums[i], max(g * nums[i], f * nums[i]));
g = min(nums[i], min(tf * nums[i], g * nums[i]));
res = max(res, f);
}
return res;
}
};
LeetCode 153. 寻找旋转排序数组中的最小值（中等）
【题目描述】
已知一个长度为 n n n 的数组，预先按照升序排列，经由 1 ∼ n 1 \sim n 1∼n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到
[4,5,6,7,0,1,2] - 若旋转 7 次，则可以得到
[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n - 1]] 旋转一次的结果为数组 [a[n - 1], a[0], a[1], a[2], ..., a[n - 2]]。
给你一个元素值互不相同的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
你必须设计一个时间复杂度为 O ( l o g n ) O(log n) O(logn) 的算法解决此问题。
【示例 1】
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
【示例 2】
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
【示例 3】
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
【提示】
n = = n u m s . l e n g t h n == nums.length n==nums.length
1 < = n < = 5000 1 <= n <= 5000 1<=n<=5000
− 5000 < = n u m s [ i ] < = 5000 -5000 <= nums[i] <= 5000 −5000<=nums[i]<=5000
nums 中的所有整数互不相同
nums 原来是一个升序排序的数组，并进行了 1 ∼ n 1 \sim n 1∼n 次旋转
【分析】
与 LeetCode 33. 很相似，而且更简单，本题只需要二分一次就行。
如果数组还是有序的，那么一定满足最后一个数大于第一个数，这种情况下的最小值就是第一个数；如果不是有序的，说明数组由两段连续的递增序列组成，最小值为后一段的第一个数，最小值左边的部分（也就是前一段连续递增序列）一定大于等于 nums[0]，自身以及右边的部分一定严格小于 nums[0]，因此二分出严格小于 nums[0] 的第一个数就是最小值。
【代码】
class Solution {
public:
int findMin(vector<int>& nums) {
if (nums[nums.size() - 1] >= nums[0]) return nums[0];
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < nums[0]) r = mid;
else l = mid + 1;
}
return nums[r];
}
};
LeetCode 154. 寻找旋转排序数组中的最小值 II（困难）
【题目描述】
已知一个长度为 n n n 的数组，预先按照升序排列，经由 1 ∼ n 1 \sim n 1∼n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到
[4,5,6,7,0,1,4] - 若旋转 7 次，则可以得到
[0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n - 1]] 旋转一次的结果为数组 [a[n - 1], a[0], a[1], a[2], ..., a[n - 2]]。
给你一个可能存在重复元素值的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
你必须尽可能减少整个过程的操作步骤。
【示例 1】
输入：nums = [1,3,5]
输出：1
【示例 2】
输入：nums = [2,2,2,0,1]
【提示】
n = = n u m s . l e n g t h n == nums.length n==nums.length
1 < = n < = 5000 1 <= n <= 5000 1<=n<=5000
− 5000 < = n u m s [ i ] < = 5000 -5000 <= nums[i] <= 5000 −5000<=nums[i]<=5000
nums 原来是一个升序排序的数组，并进行了 1 ∼ n 1 \sim n 1∼n 次旋转
进阶：这道题与上一题类似，但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
【分析】
这题和上一题的区别就在于可能会有重复元素，这样就会导致后一段序列不一定严格小于 nums[0]。例如数组 [4, 5, 1, 4, 4, 4, 4, 4] 如果直接按上一题的方法二分就会二分到最后一个数 nums[7]。
解决方法与 LeetCode 81. 一样，需要先把末尾与 nums[0] 相等的数先删去，这样就能保证二分的正确性。如果数组每个数都相同，那么最坏情况下时间复杂度就变为了 O ( n ) O(n) O(n)。
【代码】
class Solution {
public:
int findMin(vector<int>& nums) {
while (nums.size() > 1 && nums[nums.size() - 1] == nums[0]) nums.pop_back();
if (nums[nums.size() - 1] >= nums[0]) return nums[0];
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < nums[0]) r = mid;
else l = mid + 1;
}
return nums[r];
}
};
LeetCode 155. 最小栈（中等）
【题目描述】
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类：
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
【示例 1】
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
【提示】
− 2 31 < = v a l < = 2 31 − 1 -2^{31} <= val <= 2^{31} - 1 −231<=val<=231−1
pop、top 和 getMin 操作总是在非空栈上调用
push、pop、top 和 getMin最多被调用 3 ∗ 1 0 4 3 * 10^4 3∗104 次
【分析】
本题和单调栈没关系，我们要维护的是每个元素及其之前入栈的元素中的最小值，其实是 DP 的思想，即 f [ i ] f[i] f[i] 表示 1 ∼ i 1 \sim i 1∼i 的元素中的最小值，更新也很简单，每次添加一个新元素 x x x 就可以动态维护最小值：f[i] = min(f[i - 1], x)。
可以进行一个小优化，减少一些常数级的空间开销，就是当新入栈的元素 a k a_k ak 大于 f f f 的栈顶元素时就不将 a k a_k ak 入栈到 f f f 中，否则就将 a k a_k ak 入栈到 f f f 中。出栈时如果 a k a_k ak 小于等于 f f f 的栈顶元素，说明之前 a k a_k ak 有入栈过 f f f，因此顺便在 f f f 中也将栈顶元素出栈。
【代码】
【普通版】
class MinStack {
private:
stack<pair<int, int>> stk; // first 为元素值，second 为当前元素以及之前入栈元素的最小值
public:
MinStack() {}
void push(int val) {
if (stk.empty()) stk.push({val, val});
else stk.push({val, min(stk.top().second, val)});
}
void pop() {
stk.pop();
}
int top() {
return stk.top().first;
}
int getMin() {
return stk.top().second;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
【空间优化版】
class MinStack {
private:
stack<int> stk, f;
public:
MinStack() {}
void push(int val) {
if (f.empty() || val <= f.top()) f.push(val);
stk.push(val);
}
void pop() {
if (stk.top() <= f.top()) f.pop();
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return f.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/