Day4力扣打卡

打卡记录

同积元组（哈希表 + 排列组合）

链接

思路：用哈希表将数组中出现的两不同数乘积依次记录，将出现两次以上的乘积组通过排列组合计算总情况个数。

class Solution {
public:int tupleSameProduct(vector<int>& nums) {int n = nums.size(), ans = 0;unordered_map<int, int> hash;for (int i = 0; i < n; ++i)for (int j = i + 1; j < n; ++j)hash[nums[i] * nums[j]]++;for (auto& e : hash) {if (e.second > 1) ans += e.second * (e.second - 1) / 2;}return ans * 8;}
};

接雨水（单调栈）

链接

思路：横向计算填坑的面积，遍历数组时当前元素小于栈顶依次入栈，如果大于当前元素开始计算需要填补坑位的面积。（需记录底部高度）

class Solution {
public:int trap(vector<int>& height) {int ans = 0;stack<int> stack;for (int i = 0; i < height.size(); ++i) {while (!stack.empty() && height[stack.top()] <= height[i]) {int bottom = stack.top();stack.pop();if (stack.empty()) break;int h = min(height[stack.top()], height[i]) - height[bottom];ans += h * (i - stack.top() - 1);}stack.push(i);}return ans;}
};