integer最大值是多少-2373. 矩阵中的局部最大值 模拟

方法：模拟

创建答案数组

弄清***射关系，对于答案填入的位置(0,0)，相当于原数组 (0,0)到(2,2)，也就是 x 和 y 个自需要在当前和加三个位置比较最大值

填入答案，返回

class Solution {    public int[][] largestLocal(int[][] grid) {        int n = grid.length;        int[][] ans = new int[n-2][n-2];        for(int i = 0; i < n-2; i++){            for(int j = 0; j < n-2; j++){                for(int mx = 0; mx < 3; mx++){                    for(int my = 0; my < 3; my++){                        ans[i][j] = Math.max(grid[i+mx][j+my],ans[i][j]);                    }                }            }        }        return ans;    }}

func largestLocal(grid [][]int) [][]int {    n := len(grid)    ans := make([][]int,n-2)    for i:=0; i < n-2; i++{        ans[i]=make([]int,n-2)        for j:= 0; j < n-2; j++{            for mx:= 0; mx < 3; mx++{                for my:=0; my < 3; my++{                    ans[i][j] = max(grid[i+mx][j+my],ans[i][j])                }            }        }    }    return ans}
func max(a int, b int) int{if a>b{return a};return b}

时间复杂度：O(n^2t^2)integer最大值是多少，t为子矩阵
空间复杂度：O(1)integer最大值是多少，除了答案不占据额外空间
彩蛋讨论：如果希望获得的子矩阵不再固定为3，而是和原矩阵的大小有可能一致，原矩阵扩展到 1e3，该怎么写呢？
我们可以考虑，先算出一行中连续 t 个元素的最大值
然后根据上述结果再算出一列中连续 t 个元素的最大值(相当于你要求10*10个数的最大值，每行选出一个最大值，然后胜出的10个最大值里再选出一个最大值)
连续 x 个元素的最大值，可以使用堆懒删除的方式处理
class Solution {        public int[][] largestLocal(int[][] grid) {            int n = grid.length;            int[][] prey = new int[n][n];            int t = 3;            for(int i = 0; i < n; i++){                int finalI = i;                PriorityQueue pq = new PriorityQueue((a, b)->grid[finalI][b]-grid[finalI][a]);                for(int j = 0; j < n; j++){                    pq.offer(j);                    while (pq.peek()<=j-t) pq.poll();                    prey[i][j] = grid[i][pq.peek()];                }            }            int[][] ans = new int[n-t+1][n-t+1];            for(int j = t-1; j < n; j++){                int finalJ = j;                PriorityQueue pq = new PriorityQueue((a, b)->prey[b][finalJ]-prey[a][finalJ]);                for(int i = 0; i < n; i++){                    pq.offer(i);                    while (pq.peek()<=i-t) pq.poll();                    if(i>=t-1){                        ans[i-t+1][j-t+1] = prey[pq.peek()][j];                    }                }            }
            return ans;        }    }

时间复杂度：O(n^2logn)
空间复杂度：O(n^2)
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
填入复杂数组模拟矩阵答案

	

		

            
                            
                    admin网站代理                
            			
		
		


            
			 收藏            
			            
             链接