#### [121\. 买卖股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/) 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。 注意：你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 ```cpp class Solution { public: int maxProfit(vector<int>& prices) { int result = 0; int index = 0; for (int i = 0; i < prices.size(); ++i) { int profit = prices[i] - prices[index]; if (profit <= 0) { index = i; } else { if (profit > result) { result = profit; } } } return result; } }; ``` #### [146\. LRU 缓存机制](https://leetcode-cn.com/problems/lru-cache/) ```cpp class LRUCache { public: LRUCache(int capacity) : capacity(capacity) { } int get(int key) { auto it = table.find(key); if (it != table.end()) { // 先在链表中删除，再插入到头结点 lru.remove(key); lru.push_front(key); return it->second; } return -1; } void put(int key, int value) { auto it = table.find(key); if (it != table.end()) { lru.remove(key); it->second = value; lru.push_front(key); } else { if (lru.size() == capacity) { table.erase(lru.back()); lru.remove(lru.back()); } table[key] = value; lru.push_front(key); } } private: std::unordered_map<int, int> table; std::list<int> lru; int capacity; }; ```