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

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.

elem들을 그래프로 그려서 눈으로 확인하는 습관을 기르자.

가장 작은 수는 그래프가 한번이라도 꺾이고의 최소값 min을,

가장 큰 수는 그래프의 끝에서부터 한번이라고 꺾이고의 최대값 max를 찾아줬다.

한번이라도 꺾여야 하는 이유는 그렇지 않은 부분은 sort해주지 않아도 되기 때문이다.

그리고 min 과 max 가 어디서부터 시작하고 어디서 끝나는지를 찾는다.

그럼 해결.

한번 꺾이고나서 라는것을 인지하지 못해서 너무 오래걸렸다.. 이제 알았으니 잘 숙지해 두자.

class Solution {
public:
	int findUnsortedSubarray(vector<int>& nums) {
		if (nums.size() <= 1 || is_sorted(nums.begin(), nums.end()))
			return 0;
		int min = INT_MAX;
		int max = INT_MIN;
		int leftIdx, rightIdx;
		for (int i = 0; i < nums.size() - 1; ++i)
		{
			if (nums[i] > nums[i + 1])
			{
				min = std::min(min, nums[i + 1]);
			}
			if (nums[i] > nums[i + 1])
			{
				max = std::max(max, nums[i]);
			}
		}
		for (int i = 0; i < nums.size() - 1; ++i)
		{
			if (nums[i] > min)
			{
				leftIdx = i;
				break;
			}
		}
		for (int i = nums.size()- 1; i >=0; --i)
		{
			if (nums[i] < max)
			{
				rightIdx = i;
				break;
			}
		}
		return rightIdx - leftIdx + 1;
	}
};