题目简介：
给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
返回数组能分成的最多块数量。
示例 1:
1
2
3
4
5
| 输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
|
示例 2:
1
2
3
4
5
| 输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
|
提示:
n == arr.length1 <= n <= 100 <= arr[i] < narr 中每个元素都 不同
思路：
利用栈，使得每一个块的最大值能够递增排序，因此：
- 当前元素大于栈顶元素时，则直接入栈（贪心的认为这是两个块）
- 当前元素小于栈顶元素时，则不断将栈顶元素出栈（将同一个块的元素出栈），然后将这个块的最大值再压入栈即可。
最后栈中的元素便是分成的块数。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
stack<int> stk;
stk.push(arr[0]);
for(int i = 1; i < arr.size(); i++){
if(arr[i] > stk.top())
stk.push(arr[i]);
else{
int now_max = stk.top();
while(!stk.empty() && arr[i] < stk.top()){
stk.pop();
}
stk.push(now_max);
}
}
return stk.size();
}
};
|
