LeetCode 솔루션 분류
[5/3] 581. Shortest Unsorted Continuous Subarray
본문
[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
관련자료
-
링크
댓글 2
mingki님의 댓글
- 익명
- 작성일
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.
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;
}
};
austin님의 댓글
- 익명
- 작성일
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;
}
};