本文共 384 字，大约阅读时间需要 1 分钟。

问题A：

不重复未排序数组，找到每个位置左边和右边比其小且最近的元素：

单调栈，O(N)

要找到右边最小，则维护一个递增的栈，直到碰到小值，弹出比其小的值，并更新弹出元素的最近小值。

注：栈里保存下标，通过下标访问数组值。 注：重复元素同理，稍加修改即可。

---

问题B：

给定一个矩阵，只包含0和1，求1组成的最大矩阵：

dp+单调栈，O(N*M)

例如，1 0 1 1 \n 1 1 1 0 \n 1 1 1 1 \n，最大值为6

对于每行生成一维dp，其中，dp[i]表示必须以i结尾向上的最长1序列。

则，dp = 1 0 1 1 , dp = 2 1 2 0 , dp = 3 2 3 1

对于每行dp，单调栈来找必须以dp[i]为高的最大长度，乘以其高则是最大矩阵。

以第三次为例，dp = 3 2 3 1 ，则 ans = 3 6 3 4，其中最大值即为所求。

---

转载地址：http://vbwji.baihongyu.com/