456. 132 Pattern

Solution idea

Key point: $A[j]$

For each $A[j]$:

1. want to find the smallest element on its left side in $A[0\cdots j-1]$

$\Rightarrow$ loop forward + memoization

2. want to find the largest element < $A[j]$ on its right side in $A[j+1 \cdots n]$

$\Rightarrow $ loop backward + monotonic stack

So that: $A[i] < A[k] < A[j]$ for $i<j<k$

References

456. 132 Pattern, 07/22/2019

leetcode 456 132 Pattern 白板讲解