[TOC]
496. 下一个更大元素 I(简单)
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
// =========== 倒序来 ===========
/*
古城算法思路，倒序来
对于元素2，stack为空，不存在下一个更大元素。因此Map中key=2,value=-1
接着，将元素2入栈，看它是否是前面某个元素的下一个更大元素。
对于元素4，stack不为空，但由于4大于栈顶元素2且在2前面，所以元素2不是前面某个元素的下一个更大元素，所以元素2出栈。对于元素4，key=4,value=-1
接着，将元素4入栈，看它是否是前面某个元素的下一个更大元素。
对于元素3，stack不为空，且栈顶元素4大于3。对于元素3，key=3,value=4
接着，将元素3入栈，看它是否是前面某个元素的下一个更大元素。
对于元素1，stack不为空，且栈顶元素3大于1。key=1,value=3
接着，将元素1入栈。
此时nums2中所有元素考察完毕
对于数组nums1而言，对其遍历，拿考察元素作为Key，在map汇总就可以获取到下一个更大元素了。
1、用哈希表m存储每个数字的下一个最大数字
2、遍历nums2，将数字压入栈stack中
3、一旦发现当前nums2数字nums2[i]比栈顶数字要大，pop栈顶数字，更新栈顶元素的下一个最大数字值
4、遍历nums1，如果发现在m中有对应的key，说明其由下一个最大数字，返回这个数字；否则返回-1
*/
func nextGreaterElement_II(nums1 []int, nums2 []int) []int {
lenNums2 := len(nums2)
tempMap := make(map[int]int, lenNums2)
stack := make([]int, 0, lenNums2)
for i := lenNums2 - 1; i >= 0; i-- {
for len(stack) > 0 && nums2[i] >= stack[len(stack)-1] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
tempMap[nums2[i]] = -1 // 从后往前遍历的时候，key=最后一个元素，value=肯定等于-1
} else {
tempMap[nums2[i]] = stack[len(stack)-1]
}
stack = append(stack, nums2[i])
}
result := make([]int, 0, len(nums1))
for _, v := range nums1 {
result = append(result, tempMap[v])
}
return result
}
503. 下一个更大元素 II【中等】
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
// 古城算法，逆序操作
func nextGreaterElements(nums []int) []int {
nums = append(nums, nums...) // 扩大数组，制作成一个基本单调栈用例
length := len(nums)
ans := make([]int, length)
var stack = make([]int, 0)
for i := length - 1; i >= 0; i-- {
for len(stack) > 0 && nums[i] >= stack[len(stack)-1] {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
ans[i] = stack[len(stack)-1]
} else {
ans[i] = -1
}
stack = append(stack, nums[i])
}
return ans[0 : len(nums)/2]
}
739. 每日温度【中等】
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
输入: temperatures = [30,60,90]
输出: [1,1,0]
// 逆序遍历，stack中存储的是index，因为需要计算距离。
func dailyTemperatures(temperatures []int) []int {
length := len(temperatures)
ans := make([]int, length, length) // ans长度和容量都有
var stack = make([]int, 0, length) // 栈的长度为nil，有容量
for i := length - 1; i >= 0; i-- {
for len(stack) > 0 && temperatures[i] >= temperatures[stack[len(stack)-1]] {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
ans[i] = stack[len(stack)-1] - i // 计算距离
} else {
ans[i] = 0
}
stack = append(stack, i) // stack中存储的是index，因为需要计算距离。
}
return ans
}
42. 接雨水【困难】
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
输入：height = [4,2,0,3,2,5]
输出：9
84. 柱状图中最大的矩形【困难】
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
输入： heights = [2,4]
输出： 4
85. 最大矩形 【困难】
316. 去除重复字母（中等）
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
输入：s = "bcabc"
输出："abc"
输入：s = "cbacdcbc"
输出："acdb"
363. 矩形区域不超过 K 的最大数值和【困难】
给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
题目数据保证总会存在一个数值和不超过 k 的矩形区域。
输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
输入：matrix = [[2,2,-1]], k = 3
输出：3
402. 移掉 K 位数字（中等）
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 。
901. 股票价格跨度【中等】
962. 最大宽度坡（中等）
给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。找出 A 中的坡的最大宽度，如果不存在，返回 0 。
输入：[6,0,8,2,1,5]
输出：4
解释：
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.
输入：[9,8,1,0,1,9,4,0,4,1]
输出：7
解释：
最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.
1081. 不同字符的最小子序列
255. 验证前序遍历序列二叉搜索树（会员/中等）
1762. 能看到海景的建筑物（会员/中等）
有 n 座建筑物。给你一个大小为 n 的整数数组 heights 表示每一个建筑物的高度。建筑物的右边是海洋。如果建筑物可以无障碍地看到海洋，则建筑物能看到海景。确切地说，如果一座建筑物右边的所有建筑都比它 矮 时，就认为它能看到海景。返回能看到海景建筑物的下标列表（下标 从 0 开始 ），并按升序排列。
输入：heights = [4,2,3,1]
输出：[0,2,3]
解释：1 号建筑物看不到海景，因为 2 号建筑物比它高
输入：heights = [4,3,2,1]
输出：[0,1,2,3]
解释：所有的建筑物都能看到海景。
1950. 所有子数组最小值中的最大值（会员/中等）
给你一个长度为 n 的整数数组 nums ，你需要处理 n 个查询。对于第 i （0 <= i < n）个查询：你需要先找出 nums 的所有长度为 i + 1 的子数组中的 最小值 。在这些最小值中找出 最大值 作为答案。返回一个 下标从 0 开始 的长度为 n 的整数数组 ans ，ans[i] 代表第 i 个查询的答案。
输入: nums = [0,1,2,4]
输出: [4,2,1,0]
解释:
i = 0:
- 大小为 1 的子数组为 [0], [1], [2], [4]
- 有最大的最小值的子数组是 [4], 它的最小值是 4
i = 1:
- 大小为 2 的子数组为 [0,1], [1,2], [2,4]
- 有最大的最小值的子数组是 [2,4], 它的最小值是 2
i = 2:
- 大小为 3 的子数组为 [0,1,2], [1,2,4]
- 有最大的最小值的子数组是 [1,2,4], 它的最小值是 1
i = 3:
- 大小为 4 的子数组为 [0,1,2,4]
- 有最大的最小值的子数组是 [0,1,2,4], 它的最小值是 0
输入: nums = [10,20,50,10]
输出: [50,20,10,10]
解释:
i = 0:
- 大小为 1 的子数组为 [10], [20], [50], [10]
- 有最大的最小值的子数组是 [50], 它的最小值是 50
i = 1:
- 大小为 2 的子数组为 [10,20], [20,50], [50,10]
- 有最大的最小值的子数组是 [20,50], 它的最小值是 20
i = 2:
- 大小为 3 的子数组为 [10,20,50], [20,50,10]
- 有最大的最小值的子数组是 [10,20,50], 它的最小值是 10
i = 3:
- 大小为 4 的子数组为 [10,20,50,10]
- 有最大的最小值的子数组是 [10,20,50,10], 它的最小值是 10
