- [★2104. 子数组范围和](https://leetcode-cn.com/problems/sum-of-subarray-ranges/)
- 42. 接雨水
- 方法一：动态规划
- 方法二：双指针
- 方法三：按层计算
- 单调递减栈
- 901. 股票价格跨度
- 581. 最短无序连续子数组
- 456. 132 模式
- 556. 下一个更大元素 III
- 31. 下一个排列
- [71. 简化路径](https://leetcode.cn/problems/simplify-path/submissions/)
所有子数组范围的和 = 所有子数组的最大值的和 A - 所有子数组的最小值的和 B。
A = sum(a * k for a in nums) # k 是以 a 为最大值的子数组数目，ak 即 a 对和的贡献。
假设 a = nums[i]，a 的左右第一个比 a 大的数的索引分别是 left 和 right，k = (right − i) × (i − left)，其中包含 i 的区间左端点数为 i - left 个，右端点数为 right - i 个，分步为乘法。a 作为最大值的最大区间为 [left + 1, right - 1]
class Solution:
def subArrayRanges(self, nums: List[int]) -> int:
nums.append(inf)
# 单调递减栈
q, res = [-1], 0
for r, e in enumerate(nums):
# 遇到比栈顶大的数，终结栈顶元素。
while q and e > nums[q[-1]]:
i = q.pop()
left = q[-1] # if q else -1 # 在 q 预先加入 -1
res += nums[i] * (i - left) * (r - i)
q.append(r)
# 单调递增栈
q, nums[-1] = [-1], -inf
for r, e in enumerate(nums):
while q and e < nums[q[-1]]:
i = q.pop()
left = q[-1]
res -= nums[i] * (i - left) * (r - i)
q.append(r)
return res
# 方法：暴力+滑动窗口，从起点开始遍历更新最值
n, res = len(nums), 0
for i in range(n):
mi = ma = nums[i]
for j in range(i + 1, n):
ma = max(ma, nums[j])
mi = min(mi, nums[j])
res += ma - mi
return ans
class Solution {
public long subArrayRanges(int[] nums) {
int n = nums.length;
long res = 0;
ArrayDeque<Integer> q = new ArrayDeque<>();
int[] x = Arrays.copyOf(nums, n + 1);
x[n] = Integer.MAX_VALUE;
for (int i = 0; i <= n; i++){
while (!q.isEmpty() && x[i] > x[q.peek()]){
int j = q.pop();
res += (long)x[j] * (j - (q.isEmpty() ? -1 : q.peek())) * (i - j);
}
q.push(i);
}
q.clear();
x[n] = Integer.MIN_VALUE;
for (int i = 0; i <= n; i++){
while (!q.isEmpty() && x[i] < x[q.peek()]){
int j = q.pop();
res -= (long)x[j] * (j - (q.isEmpty() ? -1 : q.peek())) * (i - j);
}
q.push(i);
}
return res;
// 优化：用数组代替栈
// int n = nums.length, top = 0;
// long res = 0;
// int[] q = new int[n + 1]; // 存储下标，这里先放个 -1
// q[0] = -1;
// for (int i = 0; i <= n; i++){
// while (top > 0 && (i == n || nums[q[top]] < nums[i])){
// int j = q[top--];
// res += 1L * nums[j] * (i - j) * (j - q[top]);
// }
// q[++top] = i;
// }
// top = 0;
// q[0] = -1;
// for (int i = 0; i <= n; i++){
// while (top > 0 && (i == n || nums[q[top]] > nums[i])){
// int j = q[top--];
// res -= 1L * nums[j] * (i - j) * (j - q[top]);
// }
// q[++top] = i;
// }
// return res;
}
}
Leetcode
407. 接雨水 II
每一根柱子能接的雨水量等于柱子左右（包含柱子）最大高度的最小值减去 柱子的高度。
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n < 3: return 0
left = [height[0]] + [0] * (n - 1)
right = [0] * (n - 1) + [height[-1]]
for i in range(1, n):
left[i] = max(left[i - 1], height[i])
right[-i - 1] = max(right[-i], height[-i - 1])
return sum(min(left[i], right[i]) - height[i] for i in range(n))
# return sum(min(max(height[:i+1]), max(height[i:])) - height[i] for i in range(len(height))) if len(height) > 2 else 0
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
leftMax = rightMax = ans = 0
while left < right:
leftMax = max(leftMax, height[left])
rightMax = max(rightMax, height[right])
if height[left] < height[right]:
ans += leftMax - height[left]
left += 1
else:
ans += rightMax - height[right]
right -= 1
return ans
class Solution:
def trap(self, height: List[int]) -> int:
res = 0
left, right = 0, len(height) - 1
while right - left > 1:
tmp = min(height[left], height[right])
while left < right and tmp >= height[left]:
res += tmp - height[left]
left += 1
while left < right and tmp >= height[right]:
res += tmp - height[right]
right -= 1
return res
注意题目的性质，当后面的柱子高度比前面的低时，是无法接雨水的
当找到一根比前面高的柱子，就可以计算接到的雨水
所以使用单调递减栈
对更低的柱子入栈
更低的柱子以为这后面如果能找到高柱子，这里就能接到雨水，所以入栈把它保存起来
平地相当于高度 0 的柱子，没有什么特别影响
当出现高于栈顶的柱子时
- 说明可以对前面的柱子结算了
- 计算已经到手的雨水，然后出栈前面更低的柱子
计算雨水的时候需要注意的是
雨水区域的右边 r 指的自然是当前索引 i
底部是栈顶 st.top() ，因为遇到了更高的右边，所以它即将出栈，使用 cur 来记录它，并让它出栈
左边 l 就是新的栈顶 st.top()
雨水的区域全部确定了，水坑的高度就是左右两边更低的一边减去底部，宽度是在左右中间
使用乘法即可计算面积
int trap(vector<int>& height)
{
int ans = 0;
stack<int> st;
for (int i = 0; i < height.size(); i++)
{
while (!st.empty() && height[st.top()] < height[i])
{
int cur = st.top();
st.pop();
if (st.empty()) break;
int l = st.top();
int r = i;
int h = min(height[r], height[l]) - height[cur];
ans += (r - l - 1) * h;
}
st.push(i);
}
return ans;
}
- [★2104. 子数组范围和](https://leetcode-cn.com/problems/sum-of-subarray-ranges/)
- 42. 接雨水
- 方法一：动态规划
- 方法二：双指针
- 方法三：按层计算
- 单调递减栈
- 901. 股票价格跨度
- 581. 最短无序连续子数组
- 456. 132 模式
- 556. 下一个更大元素 III
- 31. 下一个排列
- [71. 简化路径](https://leetcode.cn/problems/simplify-path/submissions/)
Leetcode
class StockSpanner(object):
def __init__(self):
self.stack = []
def next(self, price):
weight = 1
while self.stack and self.stack[-1][0] <= price:
weight += self.stack.pop()[1]
self.stack.append((price, weight))
return weight
Leetcode
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
i, j = 0, len(nums) - 1
x = sorted(nums)
while x[i] == nums[i]:
if i == j: return 0
i += 1
while x[j] == nums[j]: j -= 1
return j - i + 1
- [★2104. 子数组范围和](https://leetcode-cn.com/problems/sum-of-subarray-ranges/)
- 42. 接雨水
- 方法一：动态规划
- 方法二：双指针
- 方法三：按层计算
- 单调递减栈
- 901. 股票价格跨度
- 581. 最短无序连续子数组
- 456. 132 模式
- 556. 下一个更大元素 III
- 31. 下一个排列
- [71. 简化路径](https://leetcode.cn/problems/simplify-path/submissions/)
Leetcode
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
n = len(nums)
candidate_k = [nums[n - 1]]
max_k = float("-inf")
for i in range(n - 2, -1, -1):
if nums[i] < max_k:
return True
while candidate_k and nums[i] > candidate_k[-1]:
max_k = candidate_k[-1]
candidate_k.pop()
if nums[i] > max_k:
candidate_k.append(nums[i])
return False
Leetcode
从后往前遍历，找到第一个升序的元素 X，X 后面为降序排列，从中找到刚好大于 X 的值，交换，排序后面元素。
class Solution:
def nextGreaterElement(self, n: int) -> int:
nums = list(str(n))
m = len(nums)
for i in range(m - 2, -1, -1):
if nums[i] < nums[i + 1]: # nums[i + 1:] 降序排列
for j in range(m - 1, i, -1):
if nums[j] > nums[i]: # 因为降序排列，直接比较即可，否则用单调栈。
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1:] = sorted(nums[i + 1:])
# break
# break
# else: return -1
# return res if (res := int(''.join(nums))) < 1 << 31 else -1
return res if (res := int(''.join(nums))) < 1 << 31 else -1
return -1
public class Solution {
public int nextGreaterElement(int n) {
char[] a = String.valueOf(n).toCharArray();
int i = a.length - 2;
while (i >= 0 && a[i + 1] <= a[i]) i--; // i 后面是降序的
if (i < 0) return -1;
int j = a.length - 1;
while (j >= 0 && a[j] <= a[i]) j--; // 找刚好比较大的数
char swap = a[i]; a[i] = a[j]; a[j] = swap;
int u = i + 1, v = a.length -1;
while (u < v){
swap = a[u]; a[u] = a[v]; a[v] = swap;
u++;v--;
}
try {
return Integer.parseInt(new String(a));
} catch (Exception e) {return -1;}
}
}
- [★2104. 子数组范围和](https://leetcode-cn.com/problems/sum-of-subarray-ranges/)
- 42. 接雨水
- 方法一：动态规划
- 方法二：双指针
- 方法三：按层计算
- 单调递减栈
- 901. 股票价格跨度
- 581. 最短无序连续子数组
- 456. 132 模式
- 556. 下一个更大元素 III
- 31. 下一个排列
- [71. 简化路径](https://leetcode.cn/problems/simplify-path/submissions/)
Leetcode
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
n, k = len(nums), 0
for i in range(n -2, -1, -1):
if nums[i + 1] > nums[i]: # 逆序找第一个峰值
for j in range(n -1, i, -1): # 逆序找第一个大于 nums[i] 的数
if nums[i] < nums[j]:
nums[i], nums[j] = nums[j], nums[i] # i 后降序排列
k = i + 1
break
break
l = n - 1
while k < l:
nums[k], nums[l] = nums[l], nums[k] # i 后变升序排列
k += 1
l -= 1
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length, k = 0, tmp;
for (int i = n - 2; i >= 0; i--){
if (nums[i + 1] > nums[i]) {
for (int j = n - 1; j > i; j--){
if (nums[j] > nums[i]){
tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
k = i + 1;
break;
}
}
break;
}
}
int l = n - 1;
while (k < l){
tmp = nums[k]; nums[k] = nums[l]; nums[l] = tmp;
k++;
l--;
}
}
}
知识点： 用队列实现栈 Deque, ArrayDeque, pollLast, offer, equals, split, join.
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<String>();
for (String p : path.split("/")) {
if ("..".equals(p)) {
if (!stack.isEmpty()) stack.pollLast();
}
else if (p != "" && !".".equals(p)) {
stack.offer(p);
}
}
return "/" + String.join("/", stack);
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）