Back to course home
0% completed
Vote For New Content
Linear time solution using monotonic stack
Dheera Jit
Jan 17, 2026
The given solution is a quadratic time solution. Here is a linear time solution:
#include <iostream> #include <vector> using namespace std; class Solution { public: int findMaxLength(const vector<int>& nums) { stack<int> goodStartPos; goodStartPos.push(0); for(int i = 1; i < nums.size(); i++){ int prevIdx = goodStartPos.top(); if(nums[i]>nums[prevIdx]){ goodStartPos.push(i); } } int maxLength = 0; for(int i = nums.size()-1; i>=0; i--){ while(!goodStartPos.empty() && nums[goodStartPos.top()]>nums[i]){ maxLength = max(maxLength, i - goodStartPos.top() + 1); goodStartPos.pop(); } } return maxLength; } };
0
0
Comments
Comments