# 下一个更大元素 II

题目链接🔗

处理循环数组有两种方法。

这个数组复制一份，将两个数组拼接在一起。

	class Solution {
	public:
	vector<int> nextGreaterElements(vector<int>& nums) {
	// 拼接一个新的 nums
	vector<int> nums1(nums.begin(), nums.end());
	nums.insert(nums.end(), nums1.begin(), nums1.end());
	// 用新的 nums 大小来初始化 result
	vector<int> result(nums.size(), -1);
	if (nums.size() == 0) return result;

	// 开始单调栈
	stack<int> st;
	st.push(0);
	for (int i = 1; i < nums.size(); i++) {
	if (nums[i] <= nums[st.top()]) st.push(i);
	else {
	while (!st.empty() && nums[i] > nums[st.top()]) {
	result[st.top()] = nums[i];
	st.pop();
	}
	st.push(i);
	}
	}
	// 最后再把结果集即 result 数组 resize 到原数组大小
	result.resize(nums.size() / 2);
	return result;
	}
	};

模拟走两边数组

	class Solution {
	public:
	vector<int> nextGreaterElements(vector<int>& nums) {
	vector<int> result(nums.size(), -1);
	if (nums.size() == 0) return result;
	stack<int> st;
	st.push(0);
	for (int i = 1; i < nums.size() * 2; i++) {
	// 模拟遍历两边 nums，注意一下都是用 i % nums.size () 来操作
	if (nums[i % nums.size()] <= nums[st.top()]) st.push(i % nums.size());
	else {
	while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
	result[st.top()] = nums[i % nums.size()];
	st.pop();
	}
	st.push(i % nums.size());
	}
	}
	return result;
	}
	};

# 接雨水

题目链接🔗

# 双指针暴力

要明确按照行还是按照列来计算。

按照列计算如图：

Alt text

按照列来计算的话，宽度一定是 1 了，再把每一列的雨水的高度求出来就可以了。

每一列雨水的高度，取决于，该列左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。

Alt text

4 的雨水高度为列 3 和列 7 的高度最小值减列 4 高度，即： min (lHeight, rHeight) - height。

列 4 的雨水高度求出来了，宽度为 1，相乘就是列 4 的雨水体积了。

	class Solution {
	public:
	int trap(vector<int>& height) {
	int sum = 0;
	for (int i = 0; i < height.size(); i++) {
	// 第一个柱子和最后一个柱子不接雨水
	if (i == 0 \|\| i == height.size() - 1) continue;

	int rHeight = height[i]; // 记录右边柱子的最高高度
	int lHeight = height[i]; // 记录左边柱子的最高高度
	for (int r = i + 1; r < height.size(); r++) {
	if (height[r] > rHeight) rHeight = height[r];
	}
	for (int l = i - 1; l >= 0; l--) {
	if (height[l] > lHeight) lHeight = height[l];
	}
	int h = min(lHeight, rHeight) - height[i];
	if (h > 0) sum += h;
	}
	return sum;
	}
	};

# 双指针优化

暴力中每到一个柱子都向两边遍历一遍，这其实是有重复计算的。

我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算。

即从左向右遍历： $maxLeft[i] = max(height[i], maxLeft[i - 1])$

从右向左遍历： $maxRight[i] = max(height[i], maxRight[i + 1])$

	class Solution {
	public:
	int trap(vector<int>& height) {
	if (height.size() <= 2) return 0;
	vector<int> maxLeft(height.size(), 0);
	vector<int> maxRight(height.size(), 0);
	int size = maxRight.size();

	// 记录每个柱子左边柱子最大高度
	maxLeft[0] = height[0];
	for (int i = 1; i < size; i++) {
	maxLeft[i] = max(height[i], maxLeft[i - 1]);
	}
	// 记录每个柱子右边柱子最大高度
	maxRight[size - 1] = height[size - 1];
	for (int i = size - 2; i >= 0; i--) {
	maxRight[i] = max(height[i], maxRight[i + 1]);
	}
	// 求和
	int sum = 0;
	for (int i = 0; i < size; i++) {
	int count = min(maxLeft[i], maxRight[i]) - height[i];
	if (count > 0) sum += count;
	}
	return sum;
	}
	};

# 单调栈解法

单调栈解法要用行来计算雨水。

Alt text

此外，从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。

因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。

Alt text

遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。

例如 5 5 1 3 这种情况。如果添加第二个 5 的时候就应该将第一个 5 的下标弹出，把第二个 5 添加到栈中。

因为我们要求宽度的时候如果遇到相同高度的柱子，需要使用最左边的柱子来计算宽度。

其实就是栈顶和栈顶的下一个元素以及要入栈的元素，三个元素来接水。

Alt text

栈里就存放下标，想要知道对应的高度，通过 height [stack.top ()] 就知道弹出的下标对应的高度了。

单调栈处理逻辑分三种：

情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height [i] < height [st.top ()]
情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height [i] == height [st.top ()]
情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height [i] > height [st.top ()]

	class Solution {
	public:
	int trap(vector<int>& height) {
	if (height.size() <= 2) return 0; // 可以不加
	stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度
	st.push(0);
	int sum = 0;
	for (int i = 1; i < height.size(); i++) {
	if (height[i] < height[st.top()]) { // 情况一
	st.push(i);
	} if (height[i] == height[st.top()]) { // 情况二
	st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。
	st.push(i);
	} else { // 情况三
	while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是 while
	int mid = st.top();
	st.pop();
	if (!st.empty()) {
	int h = min(height[st.top()], height[i]) - height[mid];
	int w = i - st.top() - 1; // 注意减一，只求中间宽度
	sum += h * w;
	}
	}
	st.push(i);
	}
	}
	return sum;
	}
	};

# 柱状图最大的矩形

题目链接🔗

# 双指针暴力

	class Solution {
	public:
	int largestRectangleArea(vector<int>& heights) {
	int sum = 0;
	for (int i = 0; i < heights.size(); i++) {
	int left = i;
	int right = i;
	for (; left >= 0; left--) {
	if (heights[left] < heights[i]) break;
	}
	for (; right < heights.size(); right++) {
	if (heights[right] < heights[i]) break;
	}
	int w = right - left - 1;
	int h = heights[i];
	sum = max(sum, w * h);
	}
	return sum;
	}
	};

# 双指针优化

和上一题接雨水思路一致。

本题要记录每个柱子左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。

	class Solution {
	public:
	int largestRectangleArea(vector<int>& heights) {
	vector<int> minLeftIndex(heights.size());
	vector<int> minRightIndex(heights.size());
	int size = heights.size();

	// 记录每个柱子左边第一个小于该柱子的下标
	minLeftIndex[0] = -1; // 注意这里初始化，防止下面 while 死循环
	for (int i = 1; i < size; i++) {
	int t = i - 1;
	// 这里不是用 if，而是不断向左寻找的过程
	while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
	minLeftIndex[i] = t;
	}
	// 记录每个柱子右边第一个小于该柱子的下标
	minRightIndex[size - 1] = size; // 注意这里初始化，防止下面 while 死循环
	for (int i = size - 2; i >= 0; i--) {
	int t = i + 1;
	// 这里不是用 if，而是不断向右寻找的过程
	while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];
	minRightIndex[i] = t;
	}
	// 求和
	int result = 0;
	for (int i = 0; i < size; i++) {
	int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
	result = max(sum, result);
	}
	return result;
	}
	};

# 单调栈

因为是找柱子两边第一个小于该柱子高的的柱子，因此单调栈是递减栈，栈顶到栈底顺序从大到小。

依旧分析三种情况：

情况一：当前遍历的元素 heights [i] 大于栈顶元素 heights [st.top ()] 的情况
情况二：当前遍历的元素 heights [i] 等于栈顶元素 heights [st.top ()] 的情况
情况三：当前遍历的元素 heights [i] 小于栈顶元素 heights [st.top ()] 的情况

	class Solution {
	public:
	int largestRectangleArea(vector<int>& heights) {
	int result = 0;
	stack<int> st;
	heights.insert(heights.begin(), 0); // 数组头部加入元素 0
	heights.push_back(0); // 数组尾部加入元素 0
	st.push(0);

	// 第一个元素已经入栈，从下标 1 开始
	for (int i = 1; i < heights.size(); i++) {
	if (heights[i] > heights[st.top()]) { // 情况一
	st.push(i);
	} else if (heights[i] == heights[st.top()]) { // 情况二
	st.pop(); // 这个可以加，可以不加，效果一样，思路不同
	st.push(i);
	} else { // 情况三
	while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是 while
	int mid = st.top();
	st.pop();
	if (!st.empty()) {
	int left = st.top();
	int right = i;
	int w = right - left - 1;
	int h = heights[mid];
	result = max(result, w * h);
	}
	}
	st.push(i);
	}
	}
	return result;
	}
	};

height 数组为什么前后加 0？

首先来说末尾为什么要加元素 0。

如果数组本身就是升序的，例如 [2,4,6,8]，那么入栈之后都是单调递减，一直都没有走情况三计算结果的哪一步，所以最后输出的就是 0 了。

那么结尾加一个 0，就会让栈里的所有元素，走到情况三的逻辑。

开头为什么要加元素 0？

如果数组本身是降序的，例如 [8,6,4,2]，在 8 入栈后，6 开始与 8 进行比较，此时我们得到 mid（8），rigt（6），但是得不到 left。

因为将 8 弹出之后，栈里没有元素了，那么为了避免空栈取值，直接跳过了计算结果的逻辑。

之后又将 6 加入栈（此时 8 已经弹出了），然后就是 4 与栈口元素 8 进行比较，周而复始，那么计算的最后结果 resutl 就是 0。

# 下一个更大元素 II

# 接雨水

# 双指针暴力

# 双指针优化

# 单调栈解法

# 柱状图最大的矩形

# 双指针暴力

# 双指针优化

# 单调栈

【代码随想录Day39】单调栈 Part.1

RESTful API入门