503. Next Greater Element II

Solution idea

My Solution

• 既然又是 Rotate/Circular array, 那么就又可以用 复制一倍的方法
  • 即，nums + nums
  • e.g. [1, 5, 7] --> [1, 5, 7, 1, 5, 7]
• 增长一倍后, 我们只用看前 n 个元素; 且每个元素往后看 n-1 个元素
  • 即, i-th element 往后看 [i+1, i+n) 左闭右开, 因为 (i+n)-th element 是它自己

Time complexity = $O(n^2)$

Better Solution

• 套用单调栈模版 - 从后往前看，挤掉栈顶矮个子!
• 用 取模 (%) 的方法 模拟 复制一倍的方法

Time complexity = $O(n)$

Similar question: 496. Next Greater Element I

Resource

单调栈结构解决三道算法题