单调队列(灵神笔记)
239 滑动窗口最大值
给你一个整数数组 nums
,有一个大小为 k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k
个数字。滑动窗口每次只向右移动一位。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2:
输入:nums = [1], k = 1
输出:[1]
提示:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
/*示例1 队列的变化
* 1. 1 2. 3 3. 3 -1 -3 4. 5 5. 5 3 6. 6 7. 7
* 注意如果是第3步 将2加入队列 滑动窗口长度(i-队首下标)大于3 删除队首元素
* 保证队首元素为滑动窗口最大值 队列单调递减
*/
int n = nums.length;
int[] ans = new int[n - k + 1];
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
//进
while (!d.isEmpty() && nums[i] >= nums[d.peekLast()]) {
d.pollLast();
}
d.addLast(i);
//出
if (i - d.peekFirst() >= k) {
d.pollFirst();
}
//更新答案
if (i >= k - 1) {
ans[i - k + 1] = nums[d.peekFirst()];
}
}
return ans;
}
}
1438 绝对差不超过限制的最长连续子数组
1438. 绝对差不超过限制的最长连续子数组 – 力扣(LeetCode)
给你一个整数数组 nums
,和一个表示限制的整数 limit
,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit
。
示例 1:
输入:nums = [8,2,4,7], limit = 4
输出:2
解释:所有子数组如下:
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此,满足题意的最长子数组的长度为 2 。
示例 2:
输入:nums = [10,1,2,4,7,2], limit = 5
输出:4
解释:满足题意的最长子数组是 [2,4,7,2],其最大绝对差 |2-7| = 5 <= 5 。
示例 3:
输入:nums = [4,2,2,2,4,4,2,2], limit = 0
输出:3
提示:
class Solution {
public int longestSubarray(int[] nums, int limit) {
//利用两个双端队列,max从左到右单调递增,队首为最大值,min相反
Deque<Integer> maxdeque = new ArrayDeque<>();
Deque<Integer> mindeque = new ArrayDeque<>();
int n = nums.length;
int right = 0, left = 0, ans = 0;
//枚举right
while (right < n) {
while (!maxdeque.isEmpty() && nums[right] > maxdeque.peekLast()) {
maxdeque.removeLast();
}
while (!mindeque.isEmpty() && nums[right] < mindeque.peekLast()) {
mindeque.removeLast();
}
maxdeque.addLast(nums[right]);
mindeque.addLast(nums[right]);
//移动left
while (maxdeque.peekFirst() - mindeque.peekFirst() > limit) {
//更新队内元素
if (maxdeque.peekFirst() == nums[left]) {
maxdeque.removeFirst();
}
if (mindeque.peekFirst() == nums[left]) {
mindeque.removeFirst();
}
left++;
}
ans = Math.max(ans, right - left + 1);
right++;
}
return ans;
}
}
2398 预算内的最多机器人数目
2398. 预算内的最多机器人数目 – 力扣(LeetCode)
你有 n
个机器人,给你两个下标从 0 开始的整数数组 chargeTimes
和 runningCosts
,两者长度都为 n
。第 i
个机器人充电时间为 chargeTimes[i]
单位时间,花费 runningCosts[i]
单位时间运行。再给你一个整数 budget
。
运行 k
个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts)
,其中 max(chargeTimes)
是这 k
个机器人中最大充电时间,sum(runningCosts)
是这 k
个机器人的运行时间之和。
请你返回在 不超过 budget
的前提下,你 最多 可以 连续 运行的机器人数目为多少。
示例 1:
输入:chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
输出:3
解释:
可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。
选择前 3 个机器人,可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ,小于 25 。
可以看出无法在 budget 以内连续运行超过 3 个机器人,所以我们返回 3 。
示例 2:
输入:chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
输出:0
解释:即使运行任何一个单个机器人,还是会超出 budget,所以我们返回 0 。
提示:
chargeTimes.length == runningCosts.length == n
1 <= n <= 5 * 104
1 <= chargeTimes[i], runningCosts[i] <= 105
1 <= budget <= 1015
class Solution {
/**
chargeTimes 3 6 1 3 4
runningCosts 2 1 3 4 5
与239滑动窗口最大值一样 队首依然是维护chargeTimes的最大元素
仅仅将固定大小的滑动窗口改为了不固定大小的双指针
*/
public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
int ans = 0;
Deque<Integer> q = new ArrayDeque<Integer>();
long sum = 0L;
for (int left = 0, right = 0; right < chargeTimes.length; right++) {
//进
while (!q.isEmpty() && chargeTimes[right] >= chargeTimes[q.peekLast()]) {
q.pollLast();
}
q.addLast(right);
sum += runningCosts[right];
//出
while (!q.isEmpty() && chargeTimes[q.peekFirst()] + (right - left + 1) * sum > budget) {
//及时清除无用的数据
if (q.peekFirst() == left) {
q.pollFirst();
}
sum -= runningCosts[left++];
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
1383 最大的团队表现值(附加)(堆)
给定两个整数 n
和 k
,以及两个长度为 n
的整数数组 speed
和 efficiency
。现有 n
名工程师,编号从 1
到 n
。其中 speed[i]
和 efficiency[i]
分别代表第 i
位工程师的速度和效率。
从这 n
名工程师中最多选择 k
名不同的工程师,使其组成的团队具有最大的团队表现值。
团队表现值 的定义为:一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
请你返回该团队的最大团队表现值,由于答案可能很大,请你返回结果对 10^9 + 7
取余后的结果。
示例 1:
输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
输出:60
解释:
我们选择工程师 2(speed=10 且 efficiency=4)和工程师 5(speed=5 且 efficiency=7)。他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。
示例 2:
输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
输出:68
解释:
此示例与第一个示例相同,除了 k = 3 。我们可以选择工程师 1 ,工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。
示例 3:
输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
输出:72
提示:
1 <= k <= n <= 10^5
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8
class Solution {
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
long maxP = 0;
int[][] engineers = new int[n][2];
for (int i = 0; i < n; i++) {
engineers[i][0] = speed[i];
engineers[i][1] = efficiency[i];
}
//排序
Arrays.sort(engineers, (a, b) -> b[1] - a[1]);
PriorityQueue<Integer> pq = new PriorityQueue<>();
long sumSpeed = 0;
int minEfficiency = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
//取出队首元素(即原有工程师中的最低速度)
if (i >= k) {
int preS = pq.poll();
sumSpeed -= preS;
}
int[] engineer = engineers[i];
pq.add(engineer[0]);
sumSpeed += engineer[0];
minEfficiency = engineer[1];
long curP = sumSpeed * minEfficiency;
maxP = Math.max(maxP, curP);
}
return (int) (maxP % (1000000007));
}
}
862 和至少为K的最短子数组
862. 和至少为 K 的最短子数组 – 力扣(LeetCode)
给你一个整数数组 nums
和一个整数 k
,找出 nums
中和至少为 k
的 最短非空子数组 ,并返回该子数组的长度。如果不存在这样的 子数组 ,返回 -1
。
子数组 是数组中 连续 的一部分。
示例 1:
输入:nums = [1], k = 1
输出:1
示例 2:
输入:nums = [1,2], k = 4
输出:-1
示例 3:
输入:nums = [2,-1,2], k = 3
输出:3
提示:
class Solution {
public int shortestSubarray(int[] nums, int k) {
int n = nums.length;
long[] pre = new long[n + 1];
pre[0] = 0;
for (int i = 0; i < n; i++) {
pre[i + 1] = pre[i] + nums[i];
}
Deque<Integer> q = new ArrayDeque<>();
int ans = n + 1;
for (int i = 0; i <= n; i++) {
long cur = pre[i];
while (!q.isEmpty() && cur - pre[q.peekFirst()] >= k) {
ans = Math.min(ans, i - q.pollFirst());
}
while (!q.isEmpty() && cur <= pre[q.peekLast()]) {
q.pollLast();
}
q.addLast(i);
}
return ans > n ? -1 : ans;
}
}
1499 满足不等式的最大值
参考题解:1499. 满足不等式的最大值 – 力扣(LeetCode)
给你一个数组 points
和一个整数 k
。数组中每个元素都表示二维平面上的点的坐标,并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi]
,并且在 1 <= i < j <= points.length
的前提下, xi < xj
总成立。
请你找出 yi + yj + |xi - xj|
的 最大值,其中 |xi - xj| <= k
且 1 <= i < j <= points.length
。
题目测试数据保证至少存在一对能够满足 |xi - xj| <= k
的点。
示例 1:
输入:points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
输出:4
解释:前两个点满足 |xi - xj| <= 1 ,代入方程计算,则得到值 3 + 0 + |1 - 2| = 4 。第三个和第四个点也满足条件,得到值 10 + -10 + |5 - 6| = 1 。
没有其他满足条件的点,所以返回 4 和 1 中最大的那个。
示例 2:
输入:points = [[0,0],[3,0],[9,2]], k = 3
输出:3
解释:只有前两个点满足 |xi - xj| <= 3 ,代入方程后得到值 0 + 0 + |0 - 3| = 3 。
提示:
2 <= points.length <= 10^5
points[i].length == 2
-10^8 <= points[i][0], points[i][1] <= 10^8
0 <= k <= 2 * 10^8
- 对于所有的
1 <= i < j <= points.length
,points[i][0] < points[j][0]
都成立。也就是说,xi
是严格递增的。
class Solution {
/** yi+yj+abs(xi-xj)=yi+yj+xj-xi=(yi-xi)+(xj+yj)
不满足abs(xi-xj)<=k 即xj-xi>k 弹他
想要得到xi我们需要用队列来保存
将(xj,yj-xj)入队 保证队列始终是单调递减
yj-xj不低于队尾的数据 弹他
*/
public int findMaxValueOfEquation(int[][] points, int k) {
int ans = Integer.MIN_VALUE;
Deque<int[]> q = new ArrayDeque<>();
for (var p : points) {
int x = p[0], y = p[1];
while (!q.isEmpty() && x - q.peekFirst()[0] > k) {
q.pollFirst();
}
if (!q.isEmpty()) {
ans = Math.max(ans, x + y + q.peekFirst()[1]);
}
while (!q.isEmpty() && q.peekLast()[1] <= y - x) {
q.pollLast();
}
q.addLast(new int[]{x, y - x});
}
return ans;
}
}
2944 购买水果需要的最少金币数
参考视频:单调队列优化 DP【力扣双周赛 118】_哔哩哔哩_bilibili
给你一个下标从 1 开始的数组 prices
,其中 prices[i]
表示你购买第 i
个水果需要花费的金币数目。
注意 ,即使你 可以 免费获得水果 j
,你仍然可以花费 prices[j]
个金币去购买它以便能免费获得接下来的 j
个水果。
请你返回获得所有水果所需要的 最少 金币数。
示例 1:
输入:prices = [3,1,2]
输出:4
解释:你可以按如下方法获得所有水果:
- 花 3 个金币购买水果 1 ,然后免费获得水果 2 。
- 花 1 个金币购买水果 2 ,然后免费获得水果 3 。
- 免费获得水果 3 。
注意,虽然你可以免费获得水果 2 ,但你还是花 1 个金币去购买它,因为这样的总花费最少。
购买所有水果需要最少花费 4 个金币。
示例 2:
输入:prices = [1,10,1,1]
输出:2
解释:你可以按如下方法获得所有水果:
- 花 1 个金币购买水果 1 ,然后免费获得水果 2 。
- 免费获得水果 2 。
- 花 1 个金币购买水果 3 ,然后免费获得水果 4 。
- 免费获得水果 4 。
购买所有水果需要最少花费 2 个金币。
提示:
1 <= prices.length <= 1000
1 <= prices[i] <= 105
记忆化搜索
class Solution {
/** 哪些水果是免费的
i+1,i+2...2i+1
下一个购买的水果 j [i+1,2i+1]
i+1到j-1都是免费获得的
*/
public int minimumCoins(int[] prices) {
int n = prices.length;
int[] cache = new int[(n + 1) / 2];
return dfs(prices, cache, 1);
}
private int dfs(int[] prices, int[] cache, int i) {
int n = prices.length;
// if (i > n) {
// return 0; // 递归边界
// }
if (i * 2 >= n) {
return prices[i - 1]; // i从1开始 优化递归边界
}
if (cache[i] != 0) {
return cache[i];
}
int ans = Integer.MAX_VALUE;
for (int j = i + 1; j <= 2 * i + 1; j++) {
ans = Math.min(ans, dfs(prices, cache, j));
}
return cache[i] = prices[i - 1] + ans;
}
}
1:1翻译成递推
class Solution {
/** 哪些水果是免费的
i+1,i+2...2i+1
下一个购买的水果 j [i+1,2i+1]
i+1到j-1都是免费获得的
*/
public int minimumCoins(int[] prices) {
int n = prices.length;
for (int i = (n + 1) / 2 - 1; i > 0; i--) {
int mn = Integer.MAX_VALUE;
for (int j = i; j <= i * 2; j++) {
mn = Math.min(mn, prices[j]);
}
prices[i - 1] += mn;
}
return prices[0];
//int[] f = new int[n + 1];
// for (int i = n; i > 0; i--) {
// if (i * 2 >= n) {
// f[i] = prices[i - 1];
// } else {
// int mn = Integer.MAX_VALUE;
// for (int j = i + 1; j <= 2 * i + 1; j++) {
// mn = Math.min(mn, f[j]);
// }
// f[i] = mn + prices[i - 1];
// }
// }
// return f[1];
}
}
单调队列优化
class Solution {
/** 求滑动窗口最小值min(f[i+1:i*2+2])
左边的小 淘汰掉 右边的大
保证队尾元素始终最小 即队列单调递减
*/
public int minimumCoins(int[] prices) {
int n = prices.length;
Deque<int[]> q = new ArrayDeque<>();
q.addLast(new int[]{n + 1, 0});// 哨兵
for (int i = n; i > 0; i--) {
while (q.peekLast()[0] > 2 * i + 1) {
q.pollLast();// 右边离开窗口
}
int f = prices[i - 1] + q.peekLast()[1];
while (f <= q.peekFirst()[1]) {
q.pollFirst();
}
q.addFirst(new int[]{i, f});// 左边进入窗口
}
return q.peekFirst()[1];
}
}
单调栈(灵神笔记)
739 每日温度
给定一个整数数组 temperatures
,表示每天的温度,返回一个数组 answer
,其中 answer[i]
是指对于第 i
天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0
来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
提示:
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] ans = new int[n];
int[] st = new int[n];
int top = -1;
for (int i = 0; i < n; i++) {
int t = temperatures[i];
//遍历到更大的元素就弹出栈顶元素
while (top >= 0 && t > temperatures[st[top]]) {
int j = st[top--];
ans[j] = i - j;
}
st[++top] = i;
}
return ans;
}
}
42 接雨水
给定 n
个非负整数表示每个宽度为 1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 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 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
class Solution {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < height.length; i++) {
//遍历到右边的板子 可以接水
while (!st.isEmpty() && height[i] >= height[st.peek()]) {
//需要三个下标 栈顶元素(右边板子) 栈顶下面的元素(中间板子) 左边的板子
//例如 5 2 1 0 4 1 1 6
//遍历到4 栈从下到上为 5 4 bottomHeight=2
int bottomHeight = height[st.pop()];
if (st.isEmpty()) {
break;
}
//返回队首元素(左板子)
int left = st.peek();
//雨水面积的高
int dh = Math.min(height[left], height[i]) - bottomHeight;
ans += dh * (i - left - 1);
}
st.push(i);
}
return ans;
}
}
1475 商品折扣后的最终价格
1475. 商品折扣后的最终价格 – 力扣(LeetCode)
给你一个数组 prices
,其中 prices[i]
是商店里第 i
件商品的价格。
商店里正在进行促销活动,如果你要买第 i
件商品,那么你可以得到与 prices[j]
相等的折扣,其中 j
是满足 j > i
且 prices[j] <= prices[i]
的 最小下标 ,如果没有满足条件的 j
,你将没有任何折扣。
请你返回一个数组,数组中第 i
个元素是折扣后你购买商品 i
最终需要支付的价格。
示例 1:
输入:prices = [8,4,6,2,3]
输出:[4,2,4,2,3]
解释:
商品 0 的价格为 price[0]=8 ,你将得到 prices[1]=4 的折扣,所以最终价格为 8 - 4 = 4 。
商品 1 的价格为 price[1]=4 ,你将得到 prices[3]=2 的折扣,所以最终价格为 4 - 2 = 2 。
商品 2 的价格为 price[2]=6 ,你将得到 prices[3]=2 的折扣,所以最终价格为 6 - 2 = 4 。
商品 3 和 4 都没有折扣。
示例 2:
输入:prices = [1,2,3,4,5]
输出:[1,2,3,4,5]
解释:在这个例子中,所有商品都没有折扣。
示例 3:
输入:prices = [10,1,1,6]
输出:[9,0,1,6]
提示:
1 <= prices.length <= 500
1 <= prices[i] <= 10^3
class Solution {
public int[] finalPrices(int[] prices) {
/** 题目让我们找到i右边最近的满足prices[j]<=prices[i]的元素
相当于 找到j左边最近的比起本身更大的元素
*/
Deque<Integer> st = new ArrayDeque<>();
int n = prices.length;
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
//遍历到的prices[i]<=栈顶元素 弹他
while (!st.isEmpty() && prices[i] <= prices[st.peekLast()]) {
int temp = st.peekLast();
st.removeLast();
ans[temp] = prices[temp] - prices[i];
}
st.add(i);
ans[i] = prices[i];
}
return ans;
}
}
901 股票价格跨度
设计一个算法收集某些股票的每日报价,并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数(从今天开始往回数,包括今天)。
示例:
输入:
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出:
[null, 1, 1, 1, 2, 1, 4, 6]
解释:
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80); // 返回 1
stockSpanner.next(60); // 返回 1
stockSpanner.next(70); // 返回 2
stockSpanner.next(60); // 返回 1
stockSpanner.next(75); // 返回 4 ,因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85); // 返回 6
提示:
class StockSpanner {
private final Deque<int[]> stack = new ArrayDeque<>();
private int curDay = -1;
public StockSpanner() {
//无需判断栈为空
stack.push(new int[]{-1, Integer.MAX_VALUE});
}
public int next(int price) {
while (price >= stack.peek()[1]) {
stack.pop();
}
int ans = ++curDay - stack.peek()[0];
stack.push(new int[]{curDay, price});
return ans;
}
}
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner obj = new StockSpanner();
* int param_1 = obj.next(price);
*/
1019 链表中的下一个更大节点
1019. 链表中的下一个更大节点 – 力扣(LeetCode)
对于列表中的每个节点,查找下一个 更大节点 的值。也就是说,对于每个节点,找到它旁边的第一个节点的值,这个节点的值 严格大于 它的值。
返回一个整数数组 answer
,其中 answer[i]
是第 i
个节点( 从1开始 )的下一个更大的节点的值。如果第 i
个节点没有下一个更大的节点,设置 answer[i] = 0
。
示例 1:
输入:head = [2,1,5]
输出:[5,5,0]
示例 2:
输入:head = [2,7,4,3,5]
输出:[7,0,5,5,0]
提示:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public int[] nextLargerNodes(ListNode head) {
int n = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
n++;
}
int[] ans = new int[n];
Deque<Integer> st = new ArrayDeque<>();// 保存节点下标
int i = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
while (!st.isEmpty() && ans[st.peek()] < cur.val) {
ans[st.pop()] = cur.val;// 更新答案
}
st.push(i);
ans[i++] = cur.val;
}
for (var index : st) {
ans[index] = 0;
}
return ans;
}
}
84 柱状图中最大的矩形
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
示例 1:
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4]
输出: 4
提示:
1 <= heights.length <=105
0 <= heights[i] <= 104
class Solution {
public int largestRectangleArea(int[] heights) {
int ans = 0;
Deque<Integer> st = new ArrayDeque<>();
int n = heights.length;
//l[i]为左边最近的比其小的下标 r[i]为右边最近的比其小的下标
int[] l = new int[n], r = new int[n];
Arrays.fill(l, -1);// 初始化-1
Arrays.fill(r, n);// 初始化n
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && heights[i] < heights[st.peekLast()]) {
r[st.pollLast()] = i;
}
st.addLast(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() && heights[i] < heights[st.peekLast()]) {
l[st.pollLast()] = i;
}
st.addLast(i);
}
for (int i = 0; i < n; i++) {
int h = heights[i];
ans = Math.max(ans, (r[i] - l[i] - 1) * h);
}
return ans;
}
}
原文地址:https://blog.csdn.net/fffffall/article/details/134761765
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_31530.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!