C++LeetCode 구현(768.정렬 가능 한 최대 블록의 2)

[LeetCode]768.Max Chunks To Make Sorted II 정렬 가능 한 최대 개수 의 2
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 to 10**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].

이 문 제 는 이전 문제 입 니 다.  Max Chunks To Make Sorted  의 확장,그 문 제 는 배열 이[0,n-1]중의 모든 숫자의 전체 배열 이 고 n 은 배열 의 길이 라 고 말 했다.이 문제 의 숫자 는 이런 제한 이 없고 n 보다 큰 숫자 일 수도 있 고 중복 되 는 숫자 도 있다.숫자 와 좌 표 는 더 이상 많은 연관 이 없 기 때문에 이전에 그 문제 에서 숫자 와 좌표 의 크기 를 비교 하 는 해법 은 틀림없이 통 하지 않 을 것 이다.우 리 는 매우 교묘 한 해법 을 살 펴 보 자.우선 우 리 는 명확 한 것 은 분 리 된 블록 을 정렬 한 후에 함께 조합 하면 원래 의 배열 과 같 을 것 이다.우 리 는 하나의 예 로 설명 한다.
2  1  4  3  4
1  2  3  4  4
1  2  3  4  4
우 리 는 첫 번 째 줄 이 원수 조 이 고,두 번 째 줄 은 정렬 한 후에 한데 연 결 된 덩어리 이 며,서로 다른 색깔 은 서로 다른 덩어리 를 대표 하고,세 번 째 줄 은 원수 조 를 직접 정렬 한 결과 이다.자세히 살 펴 보면 덩어리 를 형성 할 수 있 는 숫자 와 정렬 된 배열 의 같은 길이 의 하위 배열 의 숫자 가 같은 것 을 알 수 있다.예 를 들 어 첫 번 째 조각 은 숫자 2 와 1,그리고 3 이 고 정렬 된 앞의 두 숫자 는 1 과 2,그리고 3 이다.그러면 우 리 는 원래 배열 의 앞의 두 숫자 가 하나의 조각 으로 나 눌 수 있다 는 것 을 알 게 될 것 이다.마찬가지 로 원래 배열 의 세 번 째 숫자 와 네 번 째 숫자 는 각각 4 와 3,7 이 고 정렬 된 배열 의 대응 위치 에 있 는 숫자 의 합 도 7 이 므 로 블록 을 나 눌 수 있다 는 것 을 의미한다.주의해 야 할 것 은 배열 을 누적 할 때 정형 최대 치 를 초과 할 수 있 으 므 로 우 리 는 긴 정형 으로 저장 하면 된다 는 것 이다.바로 이렇게 간단 하고 폭력 적 인 사고 이다.시간 복잡 도 는 O(nlgn)이 고 주로 배열 의 순 서 를 매 기 는 데 쓰 인 다.왜냐하면  Max Chunks To Make Sorted  generalized 의 경우 이런 해법 은 자 연 스 럽 게 이전의 그 문 제 를 해결 할 수 있 습 니 다.그러나 시간 복잡 도가 약간 높 아 졌 습 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        long res = 0, sum1 = 0, sum2 = 0;
        vector<int> expect = arr;
        sort(expect.begin(), expect.end());
        for (int i = 0; i < arr.size(); ++i) {
            sum1 += arr[i];
            sum2 += expect[i];
            if (sum1 == sum2) ++res;
        }
        return res;
    }
};

이 문제 의 시간 복잡 도 는 선형 으로 최적화 할 수 있 지만 공간 이 좀 필요 하 다.아래 의 이러한 해법 도 상당히 교묘 하 다.우 리 는 두 개의 배열 forward 와 backward 가 필요 하 다.그 중에서 foward[i]는[0,i]범위 내 에서 가장 큰 숫자 를 나타 내 고 backward[i]는[i,n-1]범위 내 에서 가장 작은 숫자 를 나타 내 는데 사실은 이미 옮 겨 다 니 는 최대 치 와 아직 옮 겨 다 니 지 않 은 최소 치 를 알 아야 한다.왜 우 리 는 이 두 가지 가치 에 관심 이 있 습 니까?이것 은 본 해법 의 정수 이다.우 리 는 덩어리 로 나 눌 수 있 는 전 제 는 뒤의 숫자 가 현재 덩어리 중의 어떤 숫자 보다 작 으 면 안 된다 는 것 을 알 고 있다.그렇지 않 으 면 그 작은 숫자 는 앞 에 배열 할 수 없다.예 1 처럼 왜 새 덩어리 를 뜯 지 못 하 는 지,가장 작은 숫자 가 끝 에 있 기 때문이다.그러면 여기 서 우리 가 새로운 덩어리 를 떼 어 낼 수 있 는 조건 은 현재 위치 에 나타 난 최대 치가 그 후에 옮 겨 다 니 지 않 은 최소 치 보다 작 을 때 새로운 덩어리 를 떼 어 낼 수 있다 는 것 이다.예 를 들 어 예 2 에서 i=1 일 때 나타 난 최대 숫자 는 2 이 고 옮 겨 다 니 지 않 은 숫자 중 최소 값 은 3 이기 때문에 새 블록 을 뜯 을 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

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

우 리 는 공간 복잡 도 를 최적화 할 수 있 습 니 다.우 리 는 옮 겨 다 니 는 과정 에서 현재 최대 치 curMax 를 유지 할 수 있 기 때문에 전문 적 인 forward 배열 을 사용 하지 않 아 도 됩 니 다.그러나 backward 배열 은 다음 과 같 습 니 다.코드 참조: 
해법 3:

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

다음은 단조 로 운 스 택 Monotonous Stack 을 사용 하 는 해법 의 문제 도 매우 교묘 합 니 다.우 리 는 단조 로 운 스 택 을 유지 하고 스 택 꼭대기 요소 와 같은 숫자 를 만나면 스 택 에 들 어 갑 니 다.스 택 꼭대기 요소 보다 작은 숫자 를 만나면 처리 하 는 방법 이 매우 교묘 합 니 다.먼저 스 택 꼭대기 요 소 를 꺼 냅 니 다.이것 은 현재 최대 치 입 니 다.왜냐하면 우리 가 유지 하 는 것 은 단조 로 운 스 택 입 니 다.그 다음 에 우 리 는 다시 순환 을 합 니 다.만약 에 스 택 이 비어 있 지 않 고 새로운 스 택 꼭대기 요소 가 현재 숫자 보다 크 면 스 택 꼭대기 요 소 를 제거 합 니 다.이 단 계 는 정말 절묘 합 니 다.여기 서 우리 단조 로 운 스 택 의 요소 개 수 는 실제 적 으로 현재 숫자 를 옮 겨 다 니 기 전에 나 눌 수 있 는 블록 의 개수 입 니 다.우 리 는 스 택 꼭대기 보다 큰 요 소 를 만 나 서 스 택 에 눌 러 넣 습 니 다.suppose 는 새로운 블록 의 시작 입 니 다.그러나 나중에 작은 숫자 를 만 나 면 우 리 는 앞의 숫자 를 거꾸로 검사 해 야 합 니 다.우리 가 이전에 생각 했 던 것 을 덩어리 로 나 눌 수 있다 고 생각 했 던 곳 은 지금 은 뜯 을 수 없 을 것 이다.밤 을 들 어 말 하 자.
예 를 들 어 배열 은[1 0 3 3 2]이 고 우 리 는 먼저 첫 번 째 숫자 1 을 창고 에 넣 습 니 다.이때 스 택 은:
stack：1
그 다음 에 두 번 째 숫자 0 을 옮 겨 다 니 면서 스 택 꼭대기 요소 보다 작은 것 을 발견 하고 스 택 꼭대기 요소 1 을 꺼 내 서 curMax 에 저장 합 니 다.이때 스 택 이 비어 서 어떠한 조작 도 하지 않 고 curMax 를 스 택 으로 되 돌려 줍 니 다.이때 스 택 은:
stack：1
그 다음 에 세 번 째 숫자 3 을 옮 겨 다 니 며 스 택 의 꼭대기 요소 보다 크 고 스 택 에 눌 러 넣 습 니 다.이때 스 택 은:
stack：1，3
그 다음 에 네 번 째 숫자 3 을 옮 겨 다 니 면 스 택 의 꼭대기 요소 와 같 습 니 다.스 택 에 누 르 면 스 택 은 다음 과 같 습 니 다.
stack：1，3，3
그 다음 에 다섯 번 째 숫자 2 를 옮 겨 다 니 며 스 택 꼭대기 요소 보다 작 습 니 다.스 택 꼭대기 요소 3 을 꺼 내 curMax 에 저장 합 니 다.이때 새로운 스 택 꼭대기 요소 3 은 현재 숫자 2 보다 크 고 이 스 택 꼭대기 요소 3 을 제거 한 다음 에 새로운 스 택 꼭대기 요소 1 은 현재 숫자 2 보다 작 습 니 다.순환 이 끝나 면 curMax 를 스 택 으로 되 돌려 줍 니 다.이때 스 택 은:
stack：1，3
그래서 최종 적 으로 두 개의 블록,즉 stack 의 숫자 로 나 눌 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
해법 4:

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> st;
        for (int i = 0; i < arr.size(); ++i) {
            if (st.empty() || st.top() <= arr[i]) {
                st.push(arr[i]);
            } else {
                int curMax = st.top(); st.pop();
                while (!st.empty() && st.top() > arr[i]) st.pop();
                st.push(curMax);
            }
        }
        return st.size();
    }
};

여기 서 C++가 LeetCode(768.정렬 가능 한 최대 블록의 2)를 실현 하 는 것 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++가 정렬 가능 한 최대 블록의 2 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 지원 바 랍 니 다!