654. 最大二叉树

  • 递归写法

    1. 最开始的想法是预处理出每个区间的最大值的位置，保存在unordered_map中；

    2. 区间包含左右边界值，第一想法是用pair<int,int>存储，但在C++标准中没有为pair提供hash函数，即pair不能作为unordered_map的主键

    3. 解决上面的问题，其一是使用嵌套map，即unordered_map<int,unordered_map<int,int>> m;

      但尽管unordered_map查找时间复杂度接近O(1)，用这个数据结构代价还是很大的

      ”别太依赖umap了，umap不是万能的“

      这个题数据量很小，1e3，使用数组替代嵌套map后就不再超时

    4. 直接使用max_element()耗时居然比预处理每个区间的最大值更短（？）

  • 单调栈写法【先出后进】

    又一道单调栈题目：1475. 商品折扣后的最终价格

    1. 单调栈在计算每个区间的区间最值时有奇效！

      例如在本题中，可以达到O(n)的时间复杂度

    2. 一道使用单调栈计算区间最值的例题

    3. 单调栈的模板代码：

      因为新元素是一定会入栈的，所以先别急着入栈，先用while判断栈中的哪些元素要出栈，先出后进

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
         vector<XXX> vec;    // 业务数据
         stack<int> st;      // 存放 vec 的下标，此例为单调递增栈
         
         for (int i=0; i<vec.size(); ++i)
         {
             // 如果栈不为空且栈顶元素比压栈元素小，则栈顶元素出栈并作计算与更新结果，然后继续下一轮比较，直至入栈；
             // 否则，（即栈为空，或栈顶元素大于等于压栈元素），直接入栈即可
             while ( !st.empty() && vec[st.top()] < vec[i] ) {
                 st.pop();
                 // Do calculation and Update the result
           }
             st.push(i);  // vec内的元素都要入栈，但入栈的是其下标
      }