LeetCode 솔루션

[5/3] 581. Shortest Unsorted Continuous Subarray

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.02 18:59

7,476 조회
2 댓글
0 추천
0 비추천
목록 게시글 쓰기

[LeetCode 시즌 3] 2022년 5월 3일 문제입니다.

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

[Medium] 581. Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:

Input: nums = [1,2,3,4]
Output: 0

Example 3:

Input: nums = [1]
Output: 0

Constraints:

1 <= nums.length <= 104
-105 <= nums[i] <= 105

#LeetCode, #Amazon, #Microsoft, #Array, #Two Pointers, #Stack, #Greedy, #Sorting, #Monotonic Stack

링크

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/ 1799 회 연결

익명
작성일 2022.05.02 21:50

C++
Runtime: 32 ms, faster than 83.37% of C++ online submissions for Shortest Unsorted Continuous Subarray.
Memory Usage: 26.4 MB, less than 89.65% of C++ online submissions for Shortest Unsorted Continuous Subarray.

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int minVal = 100001, maxVal = -100001, minPos = 0, maxPos = n - 1;
        
        for (int i = 1; i < n; ++i) {
            if (nums[i - 1] > nums[i]) {
                minVal = min(minVal, nums[i]);
                maxVal = max(maxVal, nums[i - 1]);
            }
        }
        
        if (minVal == 100001 && maxVal == -100001) {
            return 0;
        }
        
        int i = 0;
        while (i < n && nums[i] <= minVal) {
            minPos = i++ + 1;
        }
        i = n - 1;
        while (i >= 0 && nums[i] >= maxVal) {
            maxPos = i-- - 1;
        }
        return abs(maxPos - minPos) + 1;
    }
};

익명
작성일 2022.05.03 01:58

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> v;
        for(auto n : nums) v.emplace_back(v.empty() ? n : max(v.back(), n));
        int to = 0;
        for(int i = nums.size() - 1; i > 0; --i) {
            if (v[i -1] > nums[i] && !to) to = i;
            v[i] = i == nums.size() -1 ? nums[i] : min(v[i+1], nums[i]);
        }
        for(int i = 0; i < nums.size() -1; ++i) {
            if (v[i+1] < nums[i]) return to - i + 1;
        }
        return 0;
        
    }
};