LeetCode 768. 最多能完成排序的块 II
2023-09-14 09:13:12 时间
题目描述
这个问题和“最多能完成排序的块”相似,但给定数组中的元素可以重复,输入数组最大长度为 2000
,其中的元素最大为 10**8
。
arr
是一个可能包含 重复元素 的整数数组,我们将这个数组分割成几个“块”,并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块?
数据范围
arr
的长度在 [1, 2000]
之间。
arr[i]
的大小在 [0, 10**8]
之间。
样例1:
输入: arr = [5,4,3,2,1]
输出: 1
解释:
将数组分成2块或者更多块,都无法得到所需的结果。
例如,分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3],这不是有序的数组。
样例2:
输入: arr = [2,1,3,4,4]
输出: 4
解释:
我们可以把它分成两块,例如 [2, 1], [3, 4, 4]。
然而,分成 [2, 1], [3], [4], [4] 可以得到最多的块数。
算法
(单调栈) O ( n ) O(n) O(n)
- 首先用一个栈来维护前面的集合的 最大值 ,当遇到一个新的元素的时候,如果 新元素的值 < 栈顶元素,说明该元素要放在栈顶元素的 左边,该元素和栈顶元素在同一个区间内,同时表示这个区间不完整,所以需要删除栈顶区间,重新规划。
例子
[2,1,3,4,4]
首先 2 入栈,stack[ ] = [2]
第二个数值 1 小于 栈顶元素 2,所以 2 和 1是一个区间的,需要弹出栈顶元素 2,同时计算 该区间的最大值 2 ,并且最大值 2 进栈,stack[ ] = [2]
第三个数值 3 大于 栈顶元素 2,进栈 stack[ ] = [2, 3],此时栈顶元素为 3
第四个数值 4 大于 栈顶元素 3,进栈 stack[ ] = [2, 3, 4],此时栈顶元素为 4
第五个数值 4 等于 栈顶元素 4,进栈 stack[ ] = [2, 3, 4, 4],此时栈顶元素为 4
最终的答案为 栈 的长度:4
时间复杂度
- 每个元素只会进一次栈、出一次栈、操作时间复杂度都是常数,故总时间复杂度为 O ( n ) O(n) O(n)。
空间复杂度
- 仅栈需要的空间,故空间复杂度为 O ( n ) O(n) O(n)。
C++ 代码
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
stack<int> stk;
for (int x : arr) {
int t = x;
while (stk.size() > 0 && stk.top() > x) {
t = max(t, stk.top());
stk.pop();
}
stk.push(t);
}
return stk.size();
}
};
Java 代码
class Solution {
public int maxChunksToSorted(int[] arr) {
Stack<Integer> stk = new Stack<>();
for (int x : arr) {
int t = x;
while (stk.size() > 0 && stk.peek() > x) {
t = Math.max(t, stk.peek());
stk.pop();
}
stk.push(t);
}
return stk.size();
}
}
Python3代码
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
stk = []
for x in arr:
t = x
while len(stk) > 0 and stk[-1] > x:
t = max(t, stk[-1])
stk.pop()
stk.append(t)
return len(stk)
相关文章
- [LeetCode] Valid Anagram - 字符串排序比较系列
- leetcode 之Remove Duplicates from Sorted Array(1)
- Java实现 LeetCode 769 最多能完成排序的块(单向遍历)
- Java实现 LeetCode 768 最多能完成排序的块 II(左右便利)
- Java实现 LeetCode 697 数组的度(类似于数组的map)
- Java实现 LeetCode 630 课程表 III(大小堆)
- Java实现 LeetCode 589 N叉树的前序遍历(遍历树)
- Java实现 LeetCode 561 数组拆分 I(通过排序算法改写PS:难搞)
- Java实现 LeetCode 523 连续的子数组和(ง •_•)ง
- Java实现 LeetCode 260 只出现一次的数字 III(三)
- SQK Server实现 LeetCode 175 组合两个表
- Java实现 LeetCode 80 删除排序数组中的重复项 II(二)
- Java实现 LeetCode 34 在排序数组中查找元素的第一个和最后一个位置
- Java实现 LeetCode 31下一个排列
- Java实现 Leetcode 169 求众数
- 【LeetCode算法-27】Remove Element
- 【二分】LeetCode 33. 搜索旋转排序数组【中等】
- LeetCode(81): 搜索旋转排序数组 II
- LeetCode(26): 删除排序数组中的重复项
- [LeetCode] Reverse Words in a String
- LeetCode(23):合并K个排序链表
- LeetCode-307. 区域和检索 - 数组可修改【分块处理,线段树,树状数组】
- Python 刷Leetcode题库,顺带学英语单词(47)
- leetcode 210. 课程表 II----拓扑排序篇二
- LeetCode - 200 岛屿数量
- 【LeetCode Python实现】153. 寻找旋转排序数组中的最小值(中等)
- Leetcode 2164. 对奇偶下标分别排序(可以,一次过)
- Leetcode 2089. 找出数组排序后的目标下标
- leetcode 217 Contains Duplicate 数组中是否有反复的数字
- 【LeetCode】数组中第K大的元素
- 【LeetCode】148. 排序链表