C++实现LeetCode(769.可排序的最大块数)

[LeetCode] 769.Max Chunks To Make Sorted 可排序的最大块数

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], 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 = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

Note:

  • arr will have length in range [1, 10].
  • arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

这道题给了我们一个长度为n的数组，里面的数字是[0, n-1]范围内的所有数字，无序的。现在让我们分成若干块儿，然后给每一小块儿分别排序，再组合到一起，使原数组变得有序，问我们最多能分多少块，题目中的两个例子很好的解释了题意。我们首先来分析例子1，这是一个倒序的数组，第一个数字是最大的，为4，那么我们想，这个数字4原本是应该位于数组的最后一个位置，所以中间不可能断开成新的块了，要不然数字4就没法跑到末尾去了。分析到这里，我们应该隐约有点感觉了，当前数字所在的块至少要到达坐标为当前数字大小的地方，比如数字4所在的块至少要包括i=4的那个位置。那么带着这个发现，来分析例子2。第一个数字是1，那么当前数字1所在的块至少要到 i=1 的位置，然后我们去 i=1 的位置上看，发现是数字0，并没有超过 i=1 的范围，那么前两个数就可以断开成一个新的块儿。再往后看，i=2 的位置是2，可以单独断开，后面的3和4也可以分别断开。所以其实这道题跟Jump Game II那题很像，我们需要维护一个最远能到达的位置，这里的每个数字相当于那道题中的跳力，只有当我们刚好到达最远点的时候，就可以把之前断成一个新的块儿了。

我们遍历原数组，用cur表示能到达的最远点，然后我们遍历当前位置到cur之间的所有点，遍历的同时如果遇到更大的数字就更新cur，当cur大于等于末尾数字的时候，此时不能再拆分新块儿了，返回结果res加1。否则的话说明到达了最远点，更新第一个for循环的变量i，并且结果res自增1。来看个例子:

[2 0 1 4 3]

当 i=0 时，cur=2，j=1，然后我们发现 j=1 和 j=2 的数字都不会更新cur，且cur也没有大于等于3，所以此时 j=3 的时候退出了内部的for循环，i赋值为2，结果res为1。然后此时 i=3，cur=4，4已经大于末尾的3了，直接返回res加1，即2，参见代码如下：

解法一：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int res = 0, n = arr.size();
        for (int i = 0; i < n; ++i) {
            int cur = arr[i], j = i + 1;
            for (; j <= cur; ++j) {
                cur = max(cur, arr[j]);
                if (cur >= arr.back()) return res + 1;
            }
            i = j - 1;
            ++res;
        }
        return res;
    }
};

其实这道题有更霸道的解法，我们仔细观察一些例子，可以发现断开为新块儿的地方都是当之前出现的最大值正好和当前位置坐标相等的地方，比如例子2中，当 i=1 时，之前最大的数字是1，所以可以断开。而在例子1中，当 i=4 时，才和之前出现过的最大数字4相等，此时断开也没啥意义了，因为后面已经没有数字了，所以还只是一个块儿，参见代码如下： 

解法二：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int res = 0, n = arr.size(), mx = 0;
        for (int i = 0; i < n; ++i) {
            mx = max(mx, arr[i]);
            if (mx == i) ++res;
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(769.可排序的最大块数)的文章就介绍到这了,更多相关C++实现可排序的最大块数内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(10.正则表达式匹配)

    [LeetCode] 10. Regular Expression Matching 正则表达式匹配 Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. T

  • C++实现LeetCode(验证数字)

    [LeetCode] Valid Number 验证数字 Validate if a given string can be interpreted as a decimal number. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true "

  • C++实现LeetCode(42.收集雨水)

    C++实现LeetCode(42.收集雨水)

    [LeetCode] 42. Trapping Rain Water 收集雨水 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,

  • C++实现LeetCode(8.字符串转为整数)

    [LeetCode] 8. String to Integer (atoi) 字符串转为整数 Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this ch

  • C++实现LeetCode(84.直方图中最大的矩形)

    C++实现LeetCode(84.直方图中最大的矩形)

    [LeetCode] 84. Largest Rectangle in Histogram 直方图中最大的矩形 Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of e

  • C++实现LeetCode(11.装最多水的容器)

    C++实现LeetCode(11.装最多水的容器)

    [LeetCode] 11. Container With Most Water 装最多水的容器 Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two

  • C++实现LeetCode(768.可排序的最大块数之二)

    [LeetCode] 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 cou

  • C++实现LeetCode(44.外卡匹配)

    [LeetCode] 44. Wildcard Matching 外卡匹配 Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequenc

  • C++实现LeetCode(769.可排序的最大块数)

    [LeetCode] 769.Max Chunks To Make Sorted 可排序的最大块数 Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of "chunks" (partitions), and individually sort each chunk.  After concatenating them,

  • C++实现LeetCode(60.序列排序)

    [LeetCode] 60. Permutation Sequence 序列排序 The set [1,2,3,...,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" &

  • C++实现LeetCode(75.颜色排序)

    [LeetCode] 75. Sort Colors 颜色排序 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2

  • C++实现LeetCode(148.链表排序)

    [LeetCode] 148. Sort List 链表排序 Sort a linked list in O(n log n) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 常见排序方法有

  • C++实现LeetCode(143.链表重排序)

    [LeetCode] 143.Reorder List 链表重排序 Given a singly linked list L: L0→L1→-→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→- You may not modify the values in the list's nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it t

  • asp.net DataGrid 中文字符排序的实现代码

    废话不多说,看例子: 复制代码 代码如下: <?xml version="1.0" encoding="utf-8"?> <mx:Application xmlns:mx="http://www.adobe.com/2006/mxml" layout="absolute" fontSize="12">     <mx:Script>         <!--[CDA

  • mysql通过find_in_set()函数实现where in()顺序排序

    本文章来为各位介绍一篇关于mysql 实现按 where in () 中的顺序排序,用find_in_set() 函数的教程,希望此教程能够对各位有所帮助. select * from table where id in ('783',' 769',' 814',' 1577',' 1769') order by find_in_set( id, '783, 769, 814, 1577, 1769' ) 查出来: 769 1577 814 1769 783 为什么不是 783 769 814

  • 关于javascript sort()排序你可能忽略的一点理解

    关于javascript sort()排序你可能忽略的一点理解

    前言 在Javascript数组排序中有一个sort()方法,sort()方法可以说分为两种,一种是文字数组排序,一种是数字数组排序.下面这篇文章主要和大家分享了关于最近学习javascript sort()排序发现了一点理解,下面话不多说了,来一起看看详细的介绍吧. sort()排序的原理 最近在leetcode刷题的时候遇到一个排序问题之前一直都忽略了sort排序的原理,让我们看下w3c对于sort()的说明: 如果调用该方法时没有使用参数,将按字母顺序对数组中的元素进行排序,说得更精确点,

  • c语言5个常用的排序算法实例代码

    1.插入排序 基本思想:插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕. void insertSort(vector<int>& nums) { int k = 0; for (int i = 0; i < nums.size(); ++i) { int temp = nums[i]; int j = i; for (; j > 0 && temp < nums[j-1]; --j) nums[j] =

随机推荐