头像

binacslee




离线:10小时前



单调栈另一种写法,代码更简洁

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 3010;

int n, m;
int g[N][N], h[N][N];
int l[N], r[N], stk[N];

int work(int h[]) {
    // stk 从下标 1 开始存储
    int top = 0, res = 0;
    // 遍历到 m + 1 的位置
    // 因为是在出栈时统计,为保证遍历结束时所有下标都会被统计,默认 m + 1 位置存储 0
    for (int i = 1; i <= m + 1; ++ i ) {
        while (top && h[stk[top]] >= h[i]) {
            int l = stk[top -- ];
            // 出栈时统计
            res = max(res, h[l] * (top == 0 ? i - 1 : i - stk[top] - 1));
        }
        stk[ ++ top] = i;
    }
    return res;
}

int main() {
    int p;
    cin >> n >> m >> p;
    while (p -- ) {
        int x, y;
        cin >> x >> y;
        g[x][y] = 1;
    }
    // 计算本行本列向上最多有多少可用位置
    for (int i = 1; i <= n; ++ i )
        for (int j = 1; j <= m; ++ j )
            if (!g[i][j])
                h[i][j] = h[i - 1][j] + 1;

    // for (int i = 1; i <= n; ++ i )
    //     for (int j = 1; j <= m; ++ j )
    //         cout << h[i][j] << " \n"[j == m];

    int res = 0;
    for (int i = 1; i <= n; ++ i )
        res = max(res, work(h[i]));
    cout << res << endl;

    return 0;
}


活动打卡代码 LeetCode 2. 两数相加

binacslee
3个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        my_hash,n={},len(nums)
        for i in range(n):
            if target-nums[i] in my_hash:
                return [i,my_hash[target-nums[i]]]
            else:
                my_hash[nums[i]]=i


活动打卡代码 LeetCode 1. 两数之和

binacslee
3个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if not nums:return []
        n,res=len(nums),[]
        nums.sort()
        if nums[0]>target:return []
        i,j=0,1
        for i in range(n-1):
            for j in range(i+1,n):
                if num[i]<target:
                    target-=nums[i]
                    if num[j]>target:return
                    elif nums[j]<target:j+=1
                    else:
                        res.append([i,j])
                        return 
        return res