768. Maximum number of blocks that can be sorted II
https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/
- 768. Maximum number of blocks that can be sorted II
- Question description
- Method 1: Sliding window
- Ideas
- Complexity analysis
- Code (JS/C++)
- Method 2: Monotone Stack
- Ideas
- Illustration
- Complexity analysis
- Code (JS/C++)
Title description
This question is similar to "The maximum number of blocks that can be sorted", but the elements in the given array can be repeated. The maximum length of the input array is 2000, and the maximum number of elements is 10**8. arr is an integer array that may contain duplicate elements. We split this array into several "chunks" and sort these chunks separately. Then connect them together so that the result of the connection is the same as the original array sorted in ascending order. What is the maximum number of chunks we can divide an array into? Example 1: Input: arr = [5,4,3,2,1] Output: 1 explain: Splitting the array into 2 or more chunks will not give you the desired result. For example, dividing into [5, 4], [3, 2, 1] results in [4, 5, 1, 2, 3], which is not an ordered array. Example 2: Input: arr = [2,1,3,4,4] Output: 4 explain: We can split it into two pieces, such as [2, 1], [3, 4, 4]. However, splitting into [2, 1], [3], [4], [4] gives the maximum number of blocks. Notice: The length of arr is between [1, 2000]. The size of arr[i] is between [0, 10**8]. Source: LeetCode Link: https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii The copyright belongs to Lingkou Network. For commercial reprinting, please contact the official authorizer. For non-commercial reprinting, please indicate the source.
Method 1: Sliding Window
Ideas
The question has a hint:
Each k for which some permutation of arr[:k] is equal to sorted(arr)[:k] is where we should cut each chunk.
That is, after the original array is divided into blocks, the corresponding block numbers in each block and the sorted array are the same, but the ordering is different.
Since the numbers in each block are the same, their sum is also the same. We can use a sliding window to scan the original array and the sorted array at the same time. When the sum of the numbers in the window is the same, the array is divided into blocks, just like the color blocks in the picture above.
Complexity analysis
- time complexity:
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN), N is the array length, and the array sorting time is considered to be
N
l
o
g
N
NlogN
NlogN, the sliding window traversal time of the array is
N
N
N.
- Space complexity:
O
(
N
)
O(N)
O(N), N is the array length.
Code (JS/C++)
JavaScript Code
/**
* @param {number[]} arr
* @return {number}
*/
var maxChunksToSorted = function (arr) {<!-- -->
const sorted = [...arr];
sorted.sort((a, b) => a - b);
let count = 0,
sum1 = 0,
sum2 = 0;
for (let i = 0; i < arr.length; i + + ) {<!-- -->
sum1 + = arr[i];
sum2 + = sorted[i];
if (sum1 === sum2) {<!-- -->
count + + ;
sum1 = sum2 = 0; // You don’t need this line
}
}
return count;
};
C++Code
class Solution {<!-- -->
public:
int maxChunksToSorted(vector<int> & amp; arr) {<!-- -->
int n = arr.size();
vector<int> sorted = arr;
sort(sorted.begin(), sorted.end());
long int arrSum = 0;
long int sortedSum = 0;
int chunkCount = 0;
for (int i = 0; i < n; i + + ) {<!-- -->
arrSum + = arr[i];
sortedSum + = sorted[i];
if (arrSum == sortedSum) chunkCount + + ;
}
return chunkCount;
}
};
Method 2: Monotonic stack
Ideas
According to the meaning of the question, after dividing the original array into blocks, the result after sorting each block is equal to the result after sorting the original array.
One conclusion that can be drawn is that the numbers in each block are increasing relative to the previous block (because there are repeated numbers, they may be the same), and all numbers in the next block will be greater than or equal to the previous one. All numbers in the block.
-
Because the question requires the maximum number of blocks that can be divided, we should try to divide the blocks into smaller ones so that we can divide more.
-
While traversing the array, if a number is greater than the maximum value of all previous chunks, we treat it as a new chunk.
-
If the number is less than the maximum value of some previous chunks, then these chunks are combined into one chunk (keeping the stack monotonically increasing).
Illustration
Let’s look at another example:
Complexity analysis
- time complexity:
O
(
N
)
O(N)
O(N), N is the array length.
- Space complexity:
O
(
N
)
O(N)
O(N), N is the length of the array, and the space consumed by the monotonic stack.
Code (JS/C++)
JavaScript Code
class Stack {<!-- -->
constructor() {<!-- -->
this.list = [];
}
push(val) {<!-- -->
this.list.push(val);
}
pop() {<!-- -->
return this.list.pop();
}
empty() {<!-- -->
return this.list.length === 0;
}
peek() {<!-- -->
return this.list[this.list.length - 1];
}
size() {<!-- -->
return this.list.length;
}
}
/**
* @param {number[]} arr
* @return {number}
*/
var maxChunksToSorted = function (arr) {<!-- -->
const stack = new Stack();
for (let i = 0; i < arr.length; i + + ) {<!-- -->
if (stack.empty() || stack.peek() <= arr[i]) {<!-- -->
stack.push(arr[i]);
} else {<!-- -->
const temp = stack.pop();
while (stack.peek() > arr[i]) {<!-- -->
stack.pop();
}
stack.push(temp);
}
}
return stack.size();
};
C++Code
class Solution {<!-- -->
public:
int maxChunksToSorted(vector<int> & amp; arr) {<!-- -->
stack<int> blocks;
for (int i = 0; i < arr.size(); i + + ) {<!-- -->
if (blocks.empty() || blocks.top() <= arr[i]) {<!-- -->
// a new chunk
blocks.push(arr[i]);
}
else {<!-- -->
int topNum = blocks.top();
blocks.pop();
// combine chunks
while (!blocks.empty() & amp; & amp; blocks.top() > arr[i]) {<!-- -->
blocks.pop();
}
blocks.push(topNum);
}
}
return blocks.size();
}
};
Summary
The above is all the content of this article. I hope it will be helpful to you and can solve the block II problem that can complete the sorting at most.
If you like this article, please be sure to like, collect, comment, and forward it, it will be of great help to me. It would also be great to buy me a glass of iced Coke!
It has been completed, please continue to pay attention. See you next time~