今天和大家聊的问题叫做 区域和检索 - 数组不可变，我们先来看题面：https://leetcode-cn.com/problems/range-sum-query-immutable/
给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
示例
示例: 输入: [ "0010", "0110", "0100" ] 和 x = 0, y = 2 输出: 6
解题
找最小矩形的面积，可以转化为找所有黑色像素的X, Y坐标极值，这个面积应该等于:(x2-x1+1)*(y2-y1+1)
所以一趟DFS可以找到所有黑色的点，找到每个点的时候刷新一下极值即可。
class Solution { int x1 = INT_MAX, x2 = -1; int y1 = INT_MAX, y2 = -1; public: int minArea(vector<vector<char>>& image, int x, int y) { int m = image.size(), n = image[0].size(), i, j, nx, ny, k; vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}}; queue<vector<int>> q; q.push({x,y}); image[x][y] = '0';//访问过了 while(!q.empty()) { i = q.front()[0]; j = q.front()[1]; q.pop(); x1 = min(x1, i); x2 = max(x2, i); y1 = min(y1, j); y2 = max(y2, j); for(k = 0; k < 4; ++k) { nx = i + dir[k][0]; ny = j + dir[k][1]; if(nx>=0 && nx<m && ny>=0 && ny<n && image[nx][ny]=='1') { q.push({nx, ny}); image[nx][ny] = '0';//访问过了 } } } return (x2-x1+1)*(y2-y1+1); } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
