美图
是美图（不是美团）。
昨天金融圈发生了件里程碑事件：比特币正式站上 10W 美元。
加密货币疯狂的这些年，不少人靠着上百倍（甚至上万倍的 meme 币）实现了财富自由。
但靠比特币翻身的，除了个人，还有公司。
美图公司，在国内算是一个比较特别的存在。
在移动互联网被彻底普及的那几年（2013~2016），美图公司的拳头产品「美图秀秀」，成为了最早一批「用户+日活」双破亿的国民级应用，美图公司也顺利在香港上市。
但随着进入移动互联网存量时代之后，美团公司因为「护城河不宽+变现能力有限」，开始逐渐走下坡路。
在 2021 年中概普遍不行的时候，美图公司在第一季度做了一件事：买入加密货币，分别买入大饼（BTC）和二饼（ETH)，合计成本 1 亿美元。
虽然是分批买入，但加仓时间间隔很短，最早买入时间和最后买入时间，相差只有一个月。分了三次买入，作为上市公司，需要公告股东，于是就有了「公告三次，被骂三次」的事儿。
当时不少股民都骂美图"不务正业"，确实美图公司是买在了局部高点，在买入后的 2022 年和 2023 年，都在年报中提及了亏损金额，当时也是提一次被骂一次。最高的时候，甚至浮亏超过 2 亿人民币，直到 2024 年 2 月，美图的加密货币才回到成本线附近。
再后来，随着 BTC 今年的高歌猛进，美图公司很快就从「深套」变成了「大赚」，最终以获利 7900+ 万美元离场，4 年时间，实现 +80% 的盈利。更炸裂的是，美图打算将这笔盈利作为给股东们的特别分红。
这什么神仙"小公司"？！
当时被骂得狗头一样，赚钱了该分还是分。要知道美图 2023 年全年的净利润也才 3.7 亿人民币，这一下子账面多了 5.7 亿的利润，该如何是好呀
对此，你怎么看？又是熟悉的 🍋 周五。
...
回归主题。
来一道和「美团（不是美图）」相关的算法题
题目描述
平台：LeetCode
题号：456
给你一个整数数组 nums，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足： 和 。
如果 nums 中存在 132 模式的子序列 ，返回 true；否则，返回 false。
示例 1：
输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。
示例 2：
输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
示例 3：
输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
提示：
进阶：很容易想到时间复杂度为 的解决方案，你可以设计一个时间复杂度为 或 的解决方案吗？
基本思路
朴素的做法是分别对三个数进行枚举，这样的做法是 的，数据范围是 ，稳稳超时。
事实上，这样的数据范围甚至不足以我们枚举其中两个数，然后优化找第三个数的 做法。
这时候根据数据范围会联想到树状数组，使用树状数组的复杂度是 的，可以过。但是代码量会较多一点，还需要理解离散化等前置知识。题解也不太好写。
因此，我们可以从 132 的大小特性去分析，如果在确定一个数之后，如何快速找到另外两个数（我们使用 ijk 来代指 132 结构）：
枚举
i：由于i是 132 结构中最小的数，那么相当于我们要从 i 后面，找到一个对数(j,k)，使得(j,k)都满足比i大，同时j和k之间存在j > k的关系。由于我们的遍历是单向的，因此我们可以将问题转化为找k，首先k需要比i大，同时在[i, k]之间存在比k大的数即可。枚举
j：由于j是 132 结构里最大的数，因此我们需要在j的右边中比j小的「最大」的数，在j的左边找比j小的「最小」的数。这很容易联想到单调栈，但是朴素的单调栈是帮助我们找到左边或者右边「最近」的数，无法直接满足我们「最大」和「最小」的要求，需要引入额外逻辑。枚举
k：由于k是 132 结构中的中间值，这里的分析逻辑和「枚举 i」类似，因为遍历是单向的，我们需要找到k左边的i，同时确保[i,k]之间存在比i和k大的数字。
以上三种分析方法都是可行的，但「枚举 i」的做法是最简单的。
因为如果存在 (j,k) 满足要求的话，我们只需要找到一个最大的满足条件的 k，通过与 i 的比较即可。
也许你还不理解是什么意思。没关系，我们一边证明一边说。
过程 & 证明
先说处理过程吧，我们从后往前做，维护一个「单调递减」的栈，同时使用 k 记录所有出栈元素的最大值（k 代表满足 132 结构中的 2）。
那么当我们遍历到 i，只要满足发现满足 nums[i] < k，说明我们找到了符合条件的 i j k。
举个🌰，对于样例数据 [3, 1, 4, 2]，我们知道满足 132 结构的子序列是 [1, 4, 2]，其处理逻辑是（遍历从后往前）：
枚举到 2：栈内元素为 [2]， k= INF枚举到 4：不满足「单调递减」，2 出栈更新 k，4 入栈。栈内元素为 [4]，k= 2枚举到 1：满足 nums[i] < k，说明对于i而言，后面有一个比其大的元素（满足i < k的条件），同时这个k的来源又是因为维护「单调递减」而弹出导致被更新的（满足i和k之间，有比k要大的元素）。因此我们找到了满足 132 结构的组合。
这样做的本质是：我们通过维护「单调递减」来确保已经找到了有效的 (j,k)。换句话说如果 k 有值的话，那么必然是因为有 j > k，导致的有值。也就是 132 结构中，我们找到了 32，剩下的 i （也就是 132 结构中的 1）则是通过遍历过程中与 k 的比较来找到。这样做的复杂度是 的，比树状数组还要快。
从过程上分析，是没有问题的。
搞清楚了处理过程，证明也变得十分简单。
我们不失一般性的考虑任意数组 nums，假如真实存在 ijk 符合 132 的结构（这里的 ijk 特指所有满足 132 结构要求的组合中 k 最大的那个组合）。
由于我们的比较逻辑只针对 i 和 k，而 i 是从后往前的处理的，必然会被遍历到；漏掉 ijk 的情况只能是：在遍历到 i 的时候，我们没有将 k 更新到变量中：
这时候变量的值要比真实情况下的 k要小，说明k还在栈中，而遍历位置已经到达了i，说明j和k同时在栈中，与「单调递减」的性质冲突。这时候变量的值要比真实情况下的 k要大，说明在k出栈之后，有比k更大的数值出栈了（同时必然有比变量更大的值在栈中），这时候要么与我们假设ijk是k最大的组合冲突；要么与我们遍历到的位置为i冲突。
综上，由于「单调递减」的性质，我们至少能找到「遍历过程中」所有符合条件的 ijk 中 k 最大的那个组合。
Java 代码：
class Solution {
public boolean find132pattern(int[] nums) {
Deque<Integer> d = new ArrayDeque<>();
int n = nums.length, k = -0x3f3f3f3f;
for (int i = n - 1; i >= 0; i--) {
if (nums[i] < k) return true;
while (!d.isEmpty() && d.peekLast() < nums[i]) {
// 事实上，k 的变化也具有单调性，直接使用 k = pollLast() 也是可以的
k = Math.max(k, d.pollLast());
}
d.addLast(nums[i]);
}
return false;
}
}
C++ 代码：
class Solution {
public:
bool find132pattern(vector<int>& nums) {
stack<int> st;
int n = nums.size(), k = -0x3f3f3f3f;
for(int i = n - 1; i >= 0; i--){
if(nums[i] < k) return true;
while(!st.empty() and st.top() < nums[i]) {
k = max(k,st.top()); st.pop();
}
st.push(nums[i]);
}
return false;
}
};
Python3 代码：
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
stack = []
n, k = len(nums), -0x3f3f3f3f
for i in range(n - 1,-1,-1):
if nums[i] < k:
return True
while stack and stack[-1] < nums[i]:
k = max(k,stack.pop())
stack.append(nums[i])
return False
TypeScript 代码：
function find132pattern(nums: number[]): boolean {
const d = [];
let n = nums.length, k = -0x3f3f3f3f;;
for (let i = n - 1; i >= 0; i--) {
if (nums[i] < k) return true;
while (d.length > 0 && d[d.length - 1] < nums[i]) {
k = Math.max(k, d.pop()!);
}
d.push(nums[i]);
}
return false;
};
时间复杂度： 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
