Mono-increasing stack

Key:

  • Some case should move backward as the new value we meeted is larger than it. When we meet 2 in the stack, and here we need move backward.
  • Some case we need move forward, as the following values are the mono-increaing stack: [1, 2, 5, 3, 4]
class Solution {
public:
	int findUnsortedSubarray(vector<int>& nums) {
		stack<int> st; // mono-increasing
		int left = -1, right = -2;
		for (int i = 0; i < nums.size(); i++) {
			while (!st.empty() && nums[st.top()] > nums[i]) {
				// move backward
				if (left == -1 || st.top() < left) {
					left = st.top(); // left should be the previous index
				}

				// move forward
				for (int j = i; j < nums.size() && nums[j] < nums[st.top()]; j++) {
					if (j > right) {
						right = j;
					}
				}
				st.pop();
			}
			st.push(i);
		}
		return (right - left) + 1;
	}
};

Failed test cases

[2,6,4,8,10,9,15]
[1, 2, 3, 4]
[1]
[2,1]
[1,3,2,2,2]
[1,2,3,3,3]
[2,3,3,2,4]
[1,2,5,3,4]
[1,3,5,2,4]