768. Max Chunks To Make Sorted II
This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length
2000
, and the elements could be up to10**8
.
Given an array
arr
of integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.What is the most number of chunks we could have made?
Example 1:
Input: arr = [5,4,3,2,1] Output: 1 Explanation: Splitting into two or more chunks will not return the required result. For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.Example 2:
Input: arr = [2,1,3,4,4] Output: 4 Explanation: We can split into two chunks, such as [2, 1], [3, 4, 4]. However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.
Note:
arr
will have length in range[1, 2000]
.arr[i]
will be an integer in range[0, 10**8]
.
Approach #1: Array. [Java]
class Solution { public int maxChunksToSorted(int[] arr) { int n = arr.length; int[] maxOfLeft = new int[n]; int[] minOfRight = new int[n]; maxOfLeft[0] = arr[0]; for (int i = 1; i < n; ++i) maxOfLeft[i] = Math.max(maxOfLeft[i-1], arr[i]); minOfRight[n-1] = arr[n-1]; for (int i = n-2; i >= 0; --i) minOfRight[i] = Math.min(minOfRight[i+1], arr[i]); int res = 0; for (int i = 0; i < n-1; ++i) if (maxOfLeft[i] <= minOfRight[i+1]) res++; return res+1; } }
Analysis:
Iterate through the array, each time all elements to the left are smaller (or equal) to all elements to the right, there is a new chunck.
Use two arrys to store the left max and right min to achieve O(n) time complexity. Space complexity is O(n) too.
This algorithm can be used to solve verl too.
Reference:
相关文章
- Leetcode: Minimum Moves to Equal Array Elements II
- hello world to php( mac 配置 xmapp virtual host)
- Failed to download metadata for repo ‘docker-ce-stable‘: Cannot download repomd.xml: Cannot download
- How to learn machine learning?
- EF Core | Passing navigation properties in JSON body to API controller as POST request
- How to implement a safe password history
- 微波传声技术(Voice to skull technology)
- 我的2016_To Code or Not to Code: No Question
- Need to install docker-compose(1.18.0+) by yourself first and run this script again.
- ERROR 1872 (HY000): Slave failed to initialize relay log info structure from the repository
- Unable to load authentication plugin ‘caching_sha2_password‘.
- sdut-2725-The Urge to Merge-状压DP
- 【LeetCode】122. Best Time to Buy and Sell Stock II
- LeetCode Best Time to Buy and Sell Stock I II III
- 110_leetcode_Best Time to Buy and sell Stock II
- Zero Downtime Upgrade of Oracle 10g to Oracle 11g Using GoldenGate — 1
- Attempt to fetch logical page (1:164360) in database 17 failed. It belongs to allocation unit 72057594328317952 not to 281474980642816.
- pat 1092 To Buy or Not to Buy(20 分)
- [已解决]报错run `npm audit fix` to fix them, or `npm audit` for details
- [LeetCode] Max Chunks To Make Sorted II 可排序的最大块数之二
- How to Install Eclipse C/C++ Development Tool--转
- ull, message from server: "Host '112.111.61.200' is not allowed to connect to this MySQL server"
- 122. Best Time to Buy and Sell Stock II