leetcode 刷题 log day 59

• 42. 接雨水
  【思路】

  • 双指针解法：只是单纯的、直接的、麻烦的、客观的、所有的找到了每个元素左边的最高点和右边的最高点，而当前元素能装的雨水又取决于两边最高点的最低点（最低点 - 当前元素的值），遍历所有元素计算每个元素能装多少雨水，加起来即可；
  • 动态规划：明天补~
  • 单调栈：明天补~

  //  双指针解法
  var trap = function(height) {
      let sum = 0;
      for (let i = 0; i < height.length; i++) {
          if (i === 0 || i === height.length - 1) continue;
          let lHeight = height[i], // 左边界
              rHeight = height[i];
          
          for(let l = i - 1; l >= 0; l--) {
              if (height[l] >lHeight) lHeight = height[l];
          }
  
          for(let r = i + 1; r < height.length; r++) {
              if (height[r] > rHeight) rHeight = height[r];
          }
          
          let h = Math.min(rHeight, lHeight) - height[i];
          if (h > 0) sum += h;
      }
      return sum;
  };
  

• 503. 下一个更大元素II
  【思路】这道题比之前的题多了一个环形的条件，我们只要想办法遍历两次即可，可以把 nums 数组拼成由两个 nums 组成的新数组，但这样破坏了 nums 的结构，不太好，我们可以用取余的方法来做 i % nums.length，这样就相当于遍历了两遍~

  var nextGreaterElements = function(nums) {
      let res = new Array(nums.length).fill(-1),
          stack = [];
  
      for (let i = 0; i < nums.length * 2; i++) {  // 取余可以使数组循环两遍
          while(stack.length && nums[i % nums.length] > nums[stack[stack.length - 1]]) {
              const top = stack.pop();
              res[top] = nums[i % nums.length];
          }
          stack.push(i % nums.length);
      }
      return res;
  };